Linked List
Data Structures
Introduction
• A linked list is a linear collection of data elements called nodes in
which linear representation is given by links from one node to the
next node.
• Linked list is a data structure which in turn can be used to implement
other data structures. Thus, it acts as building block to implement
data structures like stacks, queues and their variations.
• A linked list can be perceived as a train or a sequence of nodes in
which each node contains one or more data fields and a pointer to
the next node.
element
1 3 5 7 9
2000 2002 2004 2008 2010
Array
node
1 2010 3 2020 5 2030 7 2040 9 null
2000 2010 2020 2030 2040
Linked List
In linked list insertions and deletions are much faster than arrays
data pointer
node
In C, we can implement a linked list using the following code:
struct node
{ int data;
struct node *next;
};
• Node is a memory block
• Keeping track of a linked list:
– Must know the pointer to the first element of the list (called start,
head, etc.).
head
• Linked List Types:
– Single Linked List A B C
head tail
– Double Linked List A B C
head
– Circular Linked List A B C
4
Simple Linked List
START struct node
{ int data;
1 2 3 4 5 6 7 X
struct node *next;
};
• In the above linked list, every node contains two parts - one
integer and the other a pointer to the next node.
• The left part of the node which contains data may include a simple
data type, an array or a structure.
• The right part of the node contains a pointer to the next node (or
address of the next node in sequence).
• The last node will have no next node connected to it, so it will
store a special value called NULL.
Traversing Linked Lists
• We can traverse the entire linked list using a single pointer
variable called START.
• The START node contains the address of the first node; the next
part of the first node in turn stores the address of its succeeding
node.
• Using this technique the individual nodes of the list will form a
chain of nodes.
• If START = NULL, this means that the linked list is empty and
contains no nodes.
• In C, we can implement a linked list using the following code:
struct node
{ int data;
struct node *next;
};
START Pointer
START pointing to the first element of the linked list in memory
Singly Linked Lists
• A singly linked list is the simplest type of linked list in which
every node contains some data and a pointer to the next node
of the same data type.
START
1 2 3 4 5 6 7 X
ALGORITHM FOR TRAVERSING A LINKED LIST
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR->DATA
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: EXIT
Singly Linked List Node count
START
1 2 3 4 5 6 7 X
Algorithm to print the number of nodes in a linked list :
Step 1: [INITIALIZE] SET COUNT=0
Step 2: [INITIALIZE] SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR != NULL
Step 4: SET COUNT= COUNT + 1
Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 7: EXIT
Searching a Linked List
ALGORITHM TO SEARCH A LINKED LIST
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Step 3 while PTR != NULL
Step 3: IF VAL = PTR->DATA
SET POS = PTR
Go To Step 5
ELSE
SET PTR = PTR->NEXT
[END OF IF]
[END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT
Searching for Val 4 in Linked List
Inserting a Node in Linked List
A B C
tmp X Item to be
inserted
A B C
curr
12
Inserting a Node at the Beginning
1 7 3 4 2 6 5 X
START
9 1 7 3 4 2 6 5 X
START
Step 1: IF AVAIL = NULL, then Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->Next = START
Step 6: SET START = New_Node
Step 7: EXIT
In Step 1, we first check whether memory is available for the new node. If the
free memory has exhausted, then an OVERFLOW message is printed. Otherwise, if a free
memory cell is available, then we allocate space for the new node.
Inserting a Node at the End
1 7 3 4 2 6 5 X
START, PTR
1 7 3 4 2 6 5 9 X
START
Step 1: IF AVAIL = NULL, then Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->Next = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR->NEXT != NULL
Step 8: SET PTR = PTR ->NEXT
[END OF LOOP]
Step 9: SET PTR->NEXT = New_Node
Step 10: EXIT
Inserting a Node after Node that has
Value NUM
Step 1: IF AVAIL = NULL, then Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR->DATA != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR->NEXT
[END OF LOOP]
Step 10: PREPTR->NEXT = New_Node
Step 11: SET New_Node->NEXT = PTR
Step 12: EXIT
Inserting a Node before Node that has
Value NUM
Step 1: IF AVAIL = NULL, then Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR->DATA != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR->NEXT
[END OF LOOP]
Step 10: PREPTR->NEXT = New_Node
Step 11: SET New_Node->NEXT = PTR
Step 12: EXIT
Deleting the First Node
Step 1: IF START = NULL, then Write UNDERFLOW Go to Step 5
(check if the linked list exists or not )
[END OF IF]
Step 2: SET Temp = START
Step 3: SET START = START->NEXT
Step 4: FREE Temp
Step 5: EXIT
1 7 3 4 2 6 5 X
START
7 3 4 2 6 5 X
START
The computer maintains a list of all free memory cells. This list of available space is called the
free pool.
Deleting the Last Node
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR->NEXT != NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR->NEXT
[END OF LOOP]
Step 6: SET PREPTR->NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT
1 7 3 4 2 6 5 X
START, PREPTR, PTR
1 7 3 4 2 6 X 5 X
PREPTR PTR
START
Deleting the Node After a Given Node
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 10
[END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Step 5 and 6 while PREPTR->DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR->NEXT
[END OF LOOP]
Step 7: SET PREPTR->NEXT = PTR->NEXT
Step 8: FREE PTR
Step 9: EXIT
Circular Linked List
• In a circular linked list, the last node contains a pointer to the
first node of the list. We can have a circular singly listed list as
well as circular doubly linked list.
• While traversing a circular linked list, we can begin at any node
and traverse the list until we reach the same node where we had
started. Thus, a circular linked list has no beginning and no
ending.
START
1 2 3 4 5 6 7
Generally, round robin fashion is employed to allocate CPU time to resources which makes
use of the circular linked list data structure. Recursive function calls use stack data structure.
Undo Operation in text editor uses doubly linked lists. Hash tables uses singly linked lists.
Circular Linked List
Algorithm to insert a new node in the beginning
of a circular linked list:
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while PTR->NEXT != START
Step 7: PTR = PTR->NEXT
Step 8: SET PTR->NEXT = New_Node
Step 9: SET New_Node->Next = START
Step 10: SET START = New_Node
Step 11: EXIT
Circular Linked List
Circular Linked List
Algorithm to insert a new node at the end of the
circular linked list:
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->Next = START
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR->NEXT != START
Step 8: SET PTR = PTR ->NEXT
[END OF LOOP]
Step 9: SET PTR ->NEXT = New_Node
Step 10: EXIT
Circular Linked List
Circular Linked List
Algorithm to delete the first node from the circular
linked list:
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR->NEXT != START
Step 4: SET PTR = PTR->NEXT
[END OF IF]
Step 5: SET PTR->NEXT = START->NEXT
Step 6: FREE START
Step 7: SET START = PTR->NEXT
Step 8: EXIT
Circular Linked List
Circular Linked List
Algorithm to delete the last node of the circular
linked list:
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR->NEXT != START
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR->NEXT
[END OF LOOP]
Step 6: SET PREPTR->NEXT = START
Step 7: FREE PTR
Step 8: EXIT
Circular Linked List
Circular Linked List
Algorithm to delete the node after a given node from the circular
linked list:
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 9
[END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Step 5 and 6 while PREPTR->DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR->NEXT
[END OF LOOP]
Step 7: SET PREPTR->NEXT = PTR->NEXT
Step 8: FREE PTR
Step 9: EXIT
Doubly Linked List
▪ A doubly linked list or a two way linked list is a more complex type of
linked list which contains a pointer to the next as well as previous
node in the sequence. Therefore, it consists of three parts and not
just two. The three parts are data, a pointer to the next node and a
pointer to the previous node
Doubly Linked List
• In C language, the structure of a doubly linked list is given as,
struct node
{ struct node *prev;
int data;
struct node *next;
};
• The prev field of the first node and the next field of the last
node will contain NULL.
• The prev field is used to store the address of the preceding
node. This would enable to traverse the list in the backward
direction as well.
Doubly Linked List
Algorithm to insert a new node in the beginning of the doubly
linked list:
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 8
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->PREV = NULL
Step 6: SET New_Node->Next = START
Step 7: SET START-> PREV = New_Node
Step 8: SET START = New_Node
Step 9: EXIT
Doubly Linked List
Algorithm to insert a new node in the end of the doubly linked
list:
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 11
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET New_Node->Next = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR->NEXT != NULL
Step 8: SET PTR = PTR->NEXT
[END OF LOOP]
Step 9: SET PTR->NEXT = New_Node
Step 10: New_Node->PREV = PTR
Step 11: EXIT
Doubly Linked List
Algorithm to insert a new node after a node that
has value NUM:
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 8 while PTR->DATA != NUM
Step 7: SET PTR = PTR->NEXT
[END OF LOOP]
Step 8: New_Node->NEXT = PTR->NEXT
Step 9: SET New_Node->PREV = PTR
Step 10: SET PTR->NEXT->PREV = New_Node
Step 11: SET PTR->NEXT = New_Node
Step 12: EXIT
Doubly Linked List
Doubly Linked List
Algorithm to insert a new node before a node
that has value NUM:
Step 1: IF AVAIL = NULL, then
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL->NEXT
Step 4: SET New_Node->DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 8 while PTR->DATA != NUM
Step 7: SET PTR = PTR->NEXT
[END OF LOOP]
Step 8: New_Node->NEXT = PTR
Step 9: SET New_Node->PREV = PTR->PREV
Step 10: SET PTR->PREV->NEXT = New_Node
Step 11: SET PTR->PREV = New_Node
Step 12: EXIT
Doubly Linked List
Algorithm to delete the first node from the doubly linked
list:
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 6
[END OF IF]
Step 2: SET TEMP = START
Step 3: SET START = START->NEXT
Step 4: SET START->PREV = NULL
Step 5: FREE TEMP
Step 6: EXIT
Doubly Linked List
Algorithm to delete the last node of the doubly linked list
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 7
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR->NEXT != NULL
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: SET PTR->PREV->NEXT = NULL
Step 6: FREE PTR
Step 7: EXIT
Doubly Linked List
Algorithm to delete the node after a given node from the
doubly linked list:
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 9
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR->DATA != NUM
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: SET TEMP = PTR->NEXT
Step 6: SET PTR->NEXT = TEMP->NEXT
Step 7: SET TEMP->NEXT->PREV = PTR
Step 8: FREE TEMP
Step 9: EXIT
Doubly Linked List
Doubly Linked List
Algorithm to delete the node before a given node from the
doubly linked list:
Step 1: IF START = NULL, then
Write UNDERFLOW
Go to Step 9
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR->DATA != NUM
Step 4: SET PTR = PTR->NEXT
[END OF LOOP]
Step 5: SET TEMP = PTR->PREV
Step 6: SET TEMP->PREV->NEXT=PTR
Step 7: SET PTR->PREV=TEMP->PREV
Step 8: FREE TEMP
Step 9: EXIT
Array versus Linked Lists
• Arrays are suitable for:
– Inserting/deleting an element at the end.
– Randomly accessing any element.
– Searching the list for a particular value.
• Linked lists are suitable for:
– Inserting an element.
– Deleting an element.
– Applications where sequential access is required.
– In situations where the number of elements cannot
be predicted beforehand.
45
46
Dynamic Memory Allocation
• The process of allocating memory to the variables during
execution of the program or at run time is known as
dynamic memory allocation.
• C language has four library routines which allow this function.
• Till now whenever we needed an array we had declared a static array of fixed
size as int arr[100];
47
Dynamic Memory Allocation
malloc: Allocating a block of Memory malloc is declared in <stdlib.h>, so we include this
header file in any program that calls malloc.
The general syntax of malloc() is ptr =(cast-type*)malloc(byte-size);
Ex: arr=(int*)malloc(10*sizeof(int)); // is used to dynamically allocate memory
equivalent to 10 times the area of int bytes.
calloc() stands for contiguous memory allocation and is primarily used to allocate memory
for arrays.
The syntax of calloc() can be given as: ptr=(cast-type*) calloc(n,elem-size);
-> It allocates contiguous space for n blocks each of size elem-size bytes.
The only difference between malloc() and calloc() is that when we use calloc(), all bytes are
initialized to zero. calloc() returns a pointer to the first byte of the allocated region.
48
