Linked list is a special data structure in which data elements are linked to one another. Here, each element is called a node which has two parts
- Info part which stores the information.
- Address or pointer part which holds the address of next element of same type. Linked list is also known as self-referential structure.
Each element (node) of a list is comprising of two items: the data and a reference to the next node.
- The last node has a reference to NULL.
- The entry point into a linked list is called the head of the list. It should be noted that head is not a separate
- node, but the reference to the first node.
- If the list is empty then the head is a null reference.
typedef struct linkedlistnode
{
int data; //info
struct linkedlistnode * next;
}node;
Syntax of declaring a node which contains two fields in it one is for storing information and another is for storing address of other node, so that one can traverse the list.
Advantages of Linked List:
- Linked lists are dynamic data structure as they can grow and shrink during the execution time.
- Efficient memory utilisation because here memory is not pre-allocated.
- Insertions and deletions can be done very easily at the desired position.
Disadvantages of Linked List:
- More memory is required, if the number of fields are, more.
- Access to an arbitrary data item is time consuming.
Operations on Linked Lists: The following operations involve in linked list are as given below
- Creation: Used to create a lined list.
- Insertion: Used to insert a new node in linked list at the specified position. A new node may be inserted
- At the beginning of a linked list
- At the end of a linked list
- At the specified position in a linked list
- In case of empty list, a new node is inserted as a first node.
- Deletion: This operation is basically used to delete as item (a node). A node may be deleted from the
- Beginning of a linked list.
- End of a linked list.
- Specified position in the list.
- Traversing: It is a process of going through (accessing) all the nodes of a linked list from one end to the other end.
Types of Linked Lists
- Singly Linked List: In this type of linked list, each node has only one address field which points to the next node. So, the main disadvantage of this type of list is that we can’t access the predecessor of node from the current node.
- Doubly Linked List: Each node of linked list is having two address fields (or links) which help in accessing both the successor node (next node) and predecessor node (previous node).
- Circular Linked List: It has address of first node in the link (or address) field of last node.
- Circular Doubly Linked List: It has both the previous and next pointer in circular manner.
Example1: Reverse of a Singly Linked List with iterations
void reverse_list() {
node *p, *q, *r;
if(head == (mynode *)0) { return; }
p = head;
q = p->next;
p->next = (mynode *)0;
while (q != (mynode *)0) {
r = q->next;
q->next = p;
p = q;
q = r;
}
head = p;
}
Example2: Reverse of a Singly Linked List with Recursion
node* reverse_list(mynode *root) {
if(root->next!=(mynode *)0) {
reverse_list(root->next);
root->next->next=root;
return(root);
}
else { head=root; }
}
Example3: Reverse of a Doubly Linked List
void reverse( ) {
node *cur, *temp, *nextnode;
if(head==tail) return;
if(head==NULL || tail==NULL) return;
for(cur=head; cur!=NULL; ) {
temp=cur->next;
nextnode=cur->next;
cur->next=cur->prev;
cur->prev=temp;
cur=nextnode;
}
temp=head;
head=tail;
tail=temp;
}
Example 4: Finding the middle of a Linked List
struct node *middle(struct node *head) {
p=head;
q=head;
while(q->next->next!=NULL) {
p=p->next;
q=q->next->next;
}
return p;
}
Time complexity for the following operations on Singly Linked Lists of n nodes:
- Add a new node to the beginning of list: O(1)
- Add a new node to the end: O(n)
- Add a new node after k’th node: O(n)
- Search a node with a given data: O(n)
- Add a new node after a node with a given data: O(n)
- Add a new node before a node with a given data: O(n)
- Traverse all nodes: O(n)
- Delete a node from the beginning: O(1)
- Delete a node from the end: O(n)
- Delete a node with a given data: O(n)
- Delete the k’th node: O(n)
- Modify the data of all nodes in a linked list: O(n)
Time complexity for the following operations on Doubly Linked Lists of n nodes:
- Add a new node to the beginning of list: O(1)
- Add a new node to the end: O(n)
- Add a new node after k’th node: O(n)
- Search a node with a given data: O(n)
- Add a new node after a node with a given data: O(n)
- Add a new node before a node with a given data: O(n)
- Traverse all nodes: O(n)
- Delete a node from the beginning: O(1)
- Delete a node from the end: O(n)
- Delete a node with a given data: O(n)
- Delete the k’th node: O(n)
- Modify the data of all nodes in a linked list: O(n)
Time complexity for the following operations on Circular Singly Linked Lists of n nodes:
- Add a new node to the beginning of list: O(n)
- Add a new node to the end: O(n)
- Add a new node after k’th node: O(n)
- Search a node with a given data: O(n)
- Add a new node after a node with a given data: O(n)
- Add a new node before a node with a given data: O(n)
- Traverse all nodes: O(n)
- Delete a node from the beginning: O(n)
- Delete a node from the end: O(n)
- Delete a node with a given data: O(n)
- Delete the k’th node: O(n)
- Modify the data of all nodes in a linked list: O(n)
Time complexity for the following operations on Circular Doubly Linked Lists of n nodes:
- Add a new node to the beginning of list: O(1)
- Add a new node to the end: O(1)
- Add a new node after k’th node: O(n)
- Search a node with a given data: O(n)
- Add a new node after a node with a given data: O(n)
- Add a new node before a node with a given data: O(n)
- Traverse all nodes: O(n)
- Delete a node from the beginning: O(1)
- Delete a node from the end: O(1)
- Delete a node with a given data: O(n)
- Delete the k’th node: O(n)
- Modify the data of all nodes in a linked list: O(n)
"ASPIRANTS" 