In this tutorial, you are going to learn about Introduction to Linked List Data Structure.
Linked List in Data Structure
A linked list is a linear collection of data elements, in which the elements are not stored at contiguous memory locations.
- Linked list of items is arranged in order
- Size of linked list changes as items are inserted or removed
- Dynamic memory allocation is often used in linked list implementation
Advantages Over Arrays:
- Dynamic size
- Ease of insertion/deletion
Disadvantage:
- Random access is not allowed.
- Extra memory space for a pointer is required with each element of the list.
- Not cache friendly.
Representation:
- A linked list is represented by a pointer to the first node of the linked list.
- The first node is called the head.
- If the linked list is empty, then the value of the head is NULL.
Struct Node {
Typedef double item;
node* link;
}Fundamentals:
- A linked list is a sequence of items arranged one after another.
- Each item in list is connected to the next item via a link.
- Each item is placed together with the link to the next item, resulting in a simple component called a node.
Declaring a Class for Node:
struct Node
{
typedef double Item;
Item data; // data stored in node
Node *link; // pointer to next node
};
A struct is a special kind of class where all members are public. In this case there are two public member variables: data, link.
Whenever a program needs to refer to the item type, we can use the expression Node::Item.
Type of Linked List:
- Singly linked list
- Doubly linked list
- Circular linked list
Head Pointers, Tail Pointers
Usually, programs do not actually declare node variables. Instead, the list is accessed through one or more pointers to nodes.
Struct Node
{
typedef double Item;
Item data;
Node *link;
};
Node *head_ptr;
Node *tail_ptr;
Null Pointer
- The final node in the linked list does not point to a next node.
- If the link does not point to a node, its value is set to NULL.
- NULL is a special C++ constant, from the standard library facility
- NULL pointer is often written 0 (zero).
This article on 'Introduction to Linked List Data Structure' is contributed by Ritika Nagar (BCA, Sharda University). If you like TheCode11, then do follow us on Facebook, Twitter and Instagram.
