Linked Lists
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:
Types of Linked Lists
1. Single Linked Lists
2. Doubly Linked Lists
3. Circular Linked Lists
Single Linked List
1. Data part
2. Address part
Implementation
Defining a node
The Node contains 2 parts, one that is the data itself and the other which references the next node in the sequence.
In C, the node is defined as a structure . This type of a structure is called a self-referential structure where one member of the structure points to the structure of its kind.
struct Node{
int data;
struct Node *next;
};
A new Node can be created with a desirable variable name
struct Node* newNode;
The data part of the node can be accessed using the arrow character
newNode->data
Similarly,the address part can be accessed using the arrow character
newNode->next
Program for the Linked List
Doubly Linked List
Doubly linked list is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list.
The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.
Implementation
Defining a node
The Node contains 3 parts, one that is the data itself and the other which references the next node in the sequence and the other which refers the previous node.
In C, the node is defined as a structure . This type of a structure is called a self-referential structure where one member of the structure points to the structure of its kind.
struct Node{
int data;
struct Node *prev;
struct Node *next;
};
A new Node can be created with a desirable variable name
struct Node* newNode;
The data part of the node can be accessed using the arrow character
newNode->data
Similarly,the address of the next node can be accessed using the arrow character
newNode->next
Similarly,the address of the previous node can be accessed using the arrow character
newNode->prev
Program for the doubly Linked List
Circular Linked List
A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element.
That means circular linked list is similar to the single linked list except that the last node points to the first node in the list.
Implementation
Defining a node
The Node contains 2 parts, one that is the data itself and the other which references the next node in the sequence.
In C, the node is defined as a structure . This type of a structure is called a self-referential structure where one member of the structure points to the structure of its kind.
struct Node{
int data;
struct Node *next;
};
A new Node can be created with a desirable variable name
struct Node* newNode;
The data part of the node can be accessed using the arrow character
newNode->data
Similarly,the address of the next node can be accessed using the arrow character
newNode->next