DATA STRUCTURES
CSO102
WEEK-8 (DRAFT)
LINKED LIST:
A linked list is the most sought-after data structure when it comes to
handling dynamic data elements.
A linked list consists of a data element known as a node.
Each node consists of two fields: one field has data, and in the
second field, the node has an address that keeps a reference to the
next node.
LINKED LIST: OPERATIONS
IsEmpty: determine whether or not the list is empty
InsertNode: insert a new node at a particular position
FindNode: find a node with a given value
DeleteNode: delete a node with a given value
DisplayList: print all the nodes in the list
LINKED LIST: INSERTION
Locate index’th element.
Allocate memory for the new node.
Point the new node to its successor.
LINKED LIST: POSSIBLE CASES
INSERTION
1. Insert into an empty list
2. Insert in front
3. Insert at back
4. Insert in middle
LINKED LIST: DELETION
1. Find the desirable node (similar to FindNode)
2. Release the memory occupied by the found node
3. Set the pointer of the predecessor of the found node to the
successor of the found node
LINKED LIST: DELETION
LINKED LIST: DELETION- Special cases
Delete first node
Delete the node in middle or at the end of the list
LINKED LIST: FIND
?
LINKED LIST: IMPLEMENTATION
In C, we can represent a node using structures.
// A linked list node
struct Node {
int data;
struct Node* next;
};
LINKED LIST: TRAVERSAL
IMPLEMENTATION
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// This function prints contents of linked list starting
// from the given node
void printList(struct Node* n)
{
while (n != NULL) {
printf(" %d ", n->data);
n = n->next;
}
}
return 0;
}
LINKED LIST: TRAVERSAL
IMPLEMENTATION
int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// allocate 3 nodes
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1; // assign data in first node
head->next = second; // Link first node with second
second->data = 2; // assign data to second node
second->next = third;
third->data = 3; // assign data to third node
third->next = NULL;
// Function call
printList(head);
return 0;
}
LINKED LIST: VARIATIONS
Circular Linked Lists
Doubly Linked Lists
Circular Doubly Linked Lists
CIRCULAR LINKED LIST
The last node points to the first node of the list
HowThe
do last node when
we know pointswe
tohave
the first nodetraversing
finished of the listThe last(Tip:
the list? nodecheck if the
poinHow
pointer of thedo we know
current nodewhen wetohave
is equal finished traversing the list?
the head.)
(Tip:How do we know when we have finished traversing the list?
(Tip: check if the pointer of the current node is equal to the head.)
check if the pointer of the current node is equal to the head.)
ts to the first node of the list
DOUBLY LINKED LIST
Each node points to not only successor but the predecessor
There are two NULL: at the first and last nodes in the list
Advantage: given a node, it is easy to visit its predecessor.
CIRCULAR DOUBLY LINKED LIST
Circular Doubly Linked List has properties of both doubly linked list
and circular linked list.
Two consecutive elements are linked or connected by the previous
and next pointer and the last node points to the first node by the next
pointer and also the first node points to the last node by the previous
pointer.
WHY LINKED LIST OVER ARRAY
The size of the arrays is fixed.
Insertion of a new element / Deletion of a existing element in an array
of elements is expensive.
