(Yeah, it's probably going to be long README, I'll make it neat after I cover most of the DS Concepts, consider this repo as a DSAhub)
It's a DS used for storing collections of data.
- Elements are connected by pointers.
- It can grow or shrink in size during runtime.
- Memory allocation is done as list grows.
Figure: Image of a linked List
- It can be expanded in constant time.
- Unlike arrays, there is no wastage of memory upfront.
- Has O(n) access time unlike the array which has O(1).
- Memory wastage in terms of extra reference pointers.
- In some cases, it is hard to manipulate.
- Indexing: O(n)
- Insertion/Deletion at beginning: O(1)
- Insertion at the end: O(n)
- Deletion at the end: O(n)
- Insertion/Deletion in middle: O(n)
- Wasted space: O(n) (for pointers)
Each node contains a pointer which is pointed towards the next node. Last node is pointed to NULL (to indicate the end of the list).
Below, you can find a general type declaration of a singly linked list:
struct Node{
int data;
struct Node *next;
};
a) Traversing lists b) Inserting an item c) Deleting an item
Traversing How would you traverse? Simple, follow the pointers, display/count the nodes if you like and stop when the pointer points to NULL.
PseudoCode for Traversal
int traversal(struct Node *head){
struct Node *current=head;
int count=0;
while (current!=NULL){
count++;
printf("%i",¤t->data);
}
return count;
}
Time Complexity: O(n) Space Complexity: O(1)
Inserting a node in Linked List
It can be done in 3 ways:
- Inserting before head
- Inserting after tail
- Inserting at any random location in between head and tail
Inserting before head'
Logic: new node's next pointer points to head and the head pointer now must point to the new node.
-
Update next pointer of new node, to point to the current head.
-
Update the head pointer to the new node.
Inserting After Tail
Logic: Last Node's next pointer should point towards new Node. New node should point towards NULL.
Inserting at any random location between head and tail node
Note: In this case, 2 pointers need to be maintained. Pointers pointing to current node and the node previous to the current node. One point to observe here is that if you want to insert your node at position 'x', you should first traverse till position 'x-1'. We'll call this x-1th node the position node.
Logic: new node's next pointer should point towards position node's next pointer.
position node's next pointer will now point towards new node.
void insertLinkedList (struct Node **head, int data, int postition)
{
int k=1;
struct Node *p, *q, *newNode;
newNode = (Node *)malloc(sizeof(struct Node));
if (!newNode){
printf("Memory Error"); //why is it so?
return;
}
newNode->data=data;
p =*head;
// inserting at the beginning
if (position==1){
newNode->next=p;
*head=newNode;
}
else{
//Traverse the list until the position where we want to insert
while ((p!==NULL) && (k<position)){
k++;
q=p;
p=p->next;
}
p->next=newNode;
newNode->next=p;
}
}