LINKED LIST

1. An array is a data structure where elements are stored in consecutive memory location.
2. In order to store the array with consecutive memory space, it has to allocate before.
3. In array once memory allocated cannot be extended, that’s why array is called static data structure.
4. In contrast linked list is a dynamic data structure.
5. In linked list the inter connection between the elements are maintained by links are pointers.
6. An element in the linked list is called as node.
7. A node contains two fields name DATA and LINK.
8. DATA – To store the actual information.
LINK – To point to the next node.

Definitions:
A linked list is an ordered collection of finite, homogeneous data elements called nodes,where the
linear order is maintained by means of link and pointers.
Linked list can be grouped into three major groups.
1. Single linked list
2. Circular linked list.
3. Double linked list.
Single linked list:
1. In single linked list each node contains only one link which points to the next node in the list
2. Header is an empty node which is used to store the pointer to the first node.
3. Starting from the first node we can reach to its last element.
4. The node contains the link field as null, indicates the end of the list.
5. Single linked list can move from left to right only.
6. Single list is also called as one way list

Representation of linked list in memory:

There are two ways to represent a linked list in memory.
1. Static representation using array.
2. Dynamic representation using free pool of storage.
Static representation:
1. In static representation of a single linked list two arrays are maintained.
2. One array of data and another for link
3. Two parallel array of equal size are allocated and it would be sufficient to store entire linked list.

Dynamic Representation:
1. In this method there are three important things they are memory bank, Memory, Manager,
Garbage collector.
2. Memory bank- collection of free memory spaces.
3. During the node creations, when a node is required, then request is placed to MM (Memory
Manager).
4. MM searches the Memory Bank (MB) if it’s found than grants the block to the caller.
5. Memory Manager – Generally a program which manages the memory efficiently.
6. Garbage collector – Whenever the allocated note no more in use, then it has to be re-
Allocated to the memory bank.
7. The process of Memory Management includes (MB, MM, GC) are said to be dynamic
memory Management.
8. From the above figure, the list of available memory spaces and its pointer are stored in
AVAIL.
9. For a node request, the list AVAIL is searched for the block of right size.
10. In case the requested block sizes not available, then MM will return a message accordingly.
11. Suppose the block is found and let it be xy, the MM will return the points of xy to caller in a
Buffer
12. The newly availed node xy can be inserted at any position in the linked list by changing the
pointer of the concerned nodes.

Operations on a single link list:

The various possible operations on a single linked list are listed below.
1. Traversing the list.
2. Inserting a node in the list.
3. Deleting a node in the list.
4. Copying the list to make a duplicate.
5. Merging the list with another one,
6. Searching for an element.
Traversing a single linked list:
Traversing is the process of visiting each and every node in the list, its starts from the
first node and ends with last node.
Algorithm Traverse (SL)
1. ptr = HEADER –>LINK // ptr is to store the pointer of current node //
2. While (ptr # NULL) do // Continue till last node.
3. Process (ptr)
4. Ptr = ptr –>LINK // move to next node.
5. End while.
6. Stop.
Inserting a node into a single linked list:
There are various positions where a node can be inserted.
1) Inserting at the front (first element)
2) Inserting at the end (last element)
 3) Inserting at any position.
Before the discussion of above mentioned insertions, Let us assume a procedure get node
(NODE).
Get node (NODE) – To get a pointer of memory block which suits the type NODE.
Algorithm Get node.
If (AVAIL == NULL) // Avail is the pointer, that contains the collection of free storage.
Return (NULL)
Print “insufficient memory unable to allocate memory”
Else //sufficient memory is available.
Ptr = AVAIL // starts from the locations where Avail points.
While ( size of (ptr) != size of (NODE) and ptr – >LINK != NULL)
do
Ptr1 = ptr // To keep track of previous block.
Ptr = ptr –> LINK // MOVE TO THE NEXT BLOCK.
End while
If ( Size of (ptr) = size of (NODE) // memory block of right size is found.
Ptr1 -> LINK = ptr –> LINK // update the avail first.
Return (ptr)
Else
Print “the memory block is too large to fit”
Return (NULL)
End if
End if
Stop
Steps for inserting a node at the front:
1. Obtain space for new node
2. Assign data to the item field of new node
3. Set the next field of the new node to point to the start of the list
4. Change the head pointer to point to the new node.
Algorithm insert front – SL
1. new = Get node (NODE). //Get a memory block of type node and store its ptr is new.
2. If (new = NULL) then // MM return NULL on searching MB.
3. Print “Memory underflow: NO insertion”
4. Exit
5. Else // Memory available.
6. new – >LINK = Header –> LINK // change to ptr 1
7. new –> DATA = x // copy the data x the newly availed node.
8. HEADER – >LINK = new // change of ptr 2.
9. Endif
10. Stop
Inserting a node at the end of a single linked list:
Operations
1. Set the space for new node
2. Assign value to the item field
3. Set the next field of NEWNODE to NULL
4. Set the next field of previous node to NEWNODE
Algorithm insert and SL
1. new = Getnode (NODE)
2. If (New = NULL) then
3. Print “ Memory is insufficient”
4. Exit
5. Else
6. Ptr = HEADER // start from header node
7. while (ptr –> LINK # NULL ) do
8. Ptr = ptr –> LINK // change the pointer to next node.
9. End while
10. Ptr –> LINK = New // change the link field of last node.
11. New –> DATA = x //copy the cont x in new node.
12. Endif
13. Stop

Deletion of a node:
(1) Deleting the first element from list
(i) Check whether the list is empty or not Header – RLINK = NULL.
(ii) If the list is empty then exit.
(iii) If the list is not empty, then set the link field of the previous node to NULL.
(iv) Release the memory for deleted node.
Delete of front node
Operation:
1. If the node X, to be deleted is at first, store next field of x in some other variable y
2. Free the space occupied by X
3. Change the head pointer to point to the address

Algorithm Delete front – SL

1. Ptr = Header –> LINK // pointer to first node
2. If (ptr = NULL) then
3. Print “list is empty: No deletion”
4. Exit
5. Else
6. Ptrl = ptr –> LINK // ptrl points to second node
7. Header –> LINK = ptrl // next node becomes first node.
8. Return Node (ptr) // Deleted note is freed to the memory bank
9. End if
10. Stop
Deletion of the last node:
Steps to delete the last node:
1) Check whether the list is empty or not.
2) If the list is empty then exit.
3) Otherwise, the link field of the previous node is set to null
4) Release the memory for the deleted node

Algorithm delete end – SL

1. Ptr = HEADER
2. If ( ptr –> LINK = NULL) then
3. print “The list is empty”
4. Exit
5. Else
6. While (ptr –> LINK # NULL) do
7. Ptrl = ptr
8. Ptr = ptr –>LINK
9. End while
10. Ptrl –> LINK = NULL
11. Return Node (ptr)
12. Endif
13. Stop
Deletion of node from any position:
Steps to delete any node:
1. Check whether the list is empty or not
2. If the list is empty then exit
3. Otherwise, the link field of the previous node is made to point data field of the next node.
4. Release the memory for deleted nodes.

Copying a single linked list:

Algorithm copy _SL
1. Ptr = Header // current position in the master list.
2. HEADER 1 = Get node (NODE) // get node for the header of duplicate
3. Ptr 1 = HEADER 1
4. Ptr 1 –>DATA = NULL // Header does not contain any data.
5. While (ptr # NULL) do
6. new = Get node ( Node) // Get a new node form MB
7. new –> LINK = new // insert the node at the end of duplicate end.
9. new –> LINK = NULL
10. ptr 1 = new
11. ptr = ptr –> LINK // Move to the next node in the master list.
12. End While
13. Stop.
Merging two single linked list into one list:
 Suppose two linked list namely L1 and l2
 We want to merge the list L2 after L1
 Assume that Header 1 and Header 2 are the respective header of list L1 and L2.
 Merging can be done by setting the pointer of the link field of the last node with the L1
 with pointer of the first node.
 Header node in list L2 showed be returned to the collection of free storage (MB)

Algorithm merge- SL
1. Ptr = HEADER 1
2. While (ptr –> LINK # NULL) do //move to the lalst node in the list
3. ptr = ptr –> LINK
4. End while
5. Ptr –> LINK = HEADER 2 –> LINK //last node in L1 points to the first node L2.
6. Return Node (HEADER 2)
7. HEADER = HEADER 1
8. Stop.
Searching for an element in a single linked list:
Algorithm search. SL
1. Ptr = Header –> LINK // start from the first node
2. flag = 0, Location = NULL
3. While (ptr # NULL) and (flag = 0) do
4. If (ptr –> Data = key) then
5. flag = 1
6. Location = ptr
7. print “successful search”
8. Return (LOCATION)
9. Else
10. Ptr = ptr –> LINK // move to the next mode
11. Endif
12. End while
13. if(ptr=NULL)
14. print “search is unsuccessful”
15. Endif
16. Stop.

Circular Linked List:

 CLL is another form of linked list in which the last node of the list is connected to the
first node.
 Circular linked list looks like a cyclic list where there won’t be any end of list.
 Circular linked list have certain advantages over ordinary linked list.
 In ordinary list, member node is accessible from the header.
 In CLL every member node is accessible from any node.

 Insertion and deletion from a circularly linked list follow the same logic patterns used in a singly
linked list except that the last node points to the first node.
 In inserting or deleting the last node, in addition to updating the rear pointer in the header, we
must also point the link field to the first node.
 A short coming of the linear linked list is that with a given pointer to a node in linked list we
cannot reach any of the nodes that precede the node which the given pointer variable is
pointing to this disadvantage is overcome by making a little change in the structure of linear
linked list and thus making a circular linked list.
 The basic operations of the circular linked list are:
 Creation of the list
 Insertion of the node
 Modification of the node
 Deletion of the node
 Traversal of the list
 Count the number of the nodes
 To check whether a pointer points to the last node of the list ,this condition
 (Current->link==first) must be checked instead of (current->link==0).
Advantages:
1. If we are at a node, then we can go to any node. But in linear linked list it is not possible to
go to previous node.
2. It saves time when we have to go to the first node from the last node. It can be done in
single step because there is no need to traverse the in between nodes. But in double linked list,
we will have to go through in between nodes.
Disadvantages:
1. It is not easy to reverse the linked list.
2. If proper care is not taken, then the problem of infinite loop can occur.
3. If we at a node and go back to the previous node, then we can not do it in single step.
Instead we have to complete the entire circle by going through the in between nodes and then
we will reach the required node.
There are different types of circular linked list. They are
1. Circular singly linked list
2. Circular doubly linked list.
CREATION OF A LIST
The creation of the list involves three processes namely:
  Creating a node
 Reading details for a node from user
 Connect two node with the list

INSERTION OF THE NODE

 One of the most primitive operations that can be done in a singly linked list is insertion
of the node.
 Memory is to be allocated for the new node (in a similar way that is done while
creating a list) before reading the data.
 The new node will contain empty data field and empty link field.
 The data field of the new node is then stored with the information read from the user.
 The link field of the new node is assigned to NULL.
 The new node can be inserted in three different places:
1. Insertion of a node in the beginning of the list.
2. Insertion of a node in the middle of the list.
3. Insertion of a node in the end of the list.
INSERTING A NODE IN THE BEGINNING
The following steps are followed to insert a new node in the beginning of the list
 Get the new node using GETNODE () and read the details of the node using
READNODE ().
 Check whether the list is empty or not. (i.e., check whether the head pointer is
pointing (to NULL or not).
If the list is not empty then follow these steps:
 The link field of the new node is made to point.
 The data field of the first node.
 The head pointer is made to point the data field of the new node by assigning
the address of the new node.
ALGORITHM:
INSERT_FIRST (HEAD:NODE)
NEWNODE, LAST :NODE
Step1: Set NEWNODE=GETNODE ()
Step2: CALL READNODE (NEWNODE)
Step 3: If (HEAD==NULL)
Set HEAD=NEWNODE
Return
[End of If Structure]
Step 4: Set LAST=HEAD
Step 5: Repeat While (LAST->LINK!=HEAD)
Assign LAST=LAST->LINK
[End of While Loop]
Step 6: Assign LAST->LINK=NEWNODE
 Step 7: Assign NEWNODE->LINK=HEAD
Step 8: Assign HEAD=NEWNODE , END INSERT _FIRST ()

MODIFICATION OF A NODE:
A node can be modified in a list, for changing its information part. The following
steps are followed to modify a node in the list:
 Check whether the list is empty or not.(i.e., check whether the head pointer is
pointing to the NULL or not).
 Search for the node to be modified.
 Change the information part of the node.
ALGORITHM:
MODIFY_NODE (HEAD: NODE)
Step 1: If (HEAD= =NULL)
Return
[End of If Structure]
Step 2: READ condition
Step 3: Set LAST = HEAD
Step 4: REPEAT
Step 6: If (LAST->DATA= =CONDITION) then
Read LAST->DATA
Return
Else
Assign LAST=LAST->LINK
[End of IF Structure]
Step 7: Until (LAST= =HEAD)
Step 8: Print “CONDITION NOT AVAILABLE”
END MODIFY_NODE ()
DELETION OF A NODE
Another primitive operation that can be done in a circular singly linked list is the
deletion of the node. Memory is to be released for the node to be deleted. A node can be deleted
from the list from three places:
1. Deletion of the first node from the list.
 2. Deletion of the intermediate node from the list.
3. Deletion of the last node from the list.

DELETION OF THE FIRST NODE

The following steps are to be followed while deleting z node from the beginning of the list:
 Check whether the list is empty or not(i.e., check whether the head pointer
is pointing NULL or not).
 Set head pointer to the second node in the list(by assigning its address).
 Release the memory for the deleted node.
ALGORITHM
DELETE _FIRST(HEAD :NODE)
Step 1: If (HEAD==NULL)
PRINT “LIST IS EMPTY”
Return
[End of IF Structure]
Step 2: If (HEAD ->LINK==HEAD)Then
Set (DELNODE==HEAD)
Set (HEAD==NULL)
Print ”DELETED DATA IS” ,DELNODE->DATA
CALL RELEASENODE (DEL NODE)
[End of If Structure]
Step 3: Set LAST=HEAD
Step 4: Repeat
Assign PREV=LAST
Assign LAST=LAST->LINK
Until (LAST->LINK==HEAD)
Step 5: DELNODE=LAST
Step 6: PREV->LINK=HEAD
Step 7: Print the deleted data is DELNODE->DATA
Step 8: CALL RELEASENODE (DELNODE)
END DELETE _FIRST ()
TRAVERSAL OF A LIST:
To read the information or to display the information in the list ,we must traverse the node
one by one starting from the first node until the last node. Traversing a circular list involves:
 Check whether the head pointer is pointing NULL or not.
 Display the information in the data field stored in the head pointer.
 Traverse the node one by one by advancing the head pointer.
ALGORITHM
VIEW (HEAD: NODE)
Step 1: LIST=HEAD
Step 2: If (LIST==NULL)
PRINT”LIST IS EMPTY”
[END OF IF STRUCTURE]
Step 3: Repeat
Step 4: print “the data is “,LIST->DATA
Step 5: LIST=LIST->LINK
Step 6: Until (LIST==HEAD)
END VIEW()
DOUBLY LINKED LIST: (DLL)
The doubly or two –way linked list uses double set of pointers, one pointing to the next item
and other pointing to the preceding item.
It can be traversed in two directions either from the beginning of the list to the end or in the
back ward direction from end of the list to the beginning.

The previous address field of a node contains address of the previous node. The field is also referred as
the backward link field. The data field stores the information part of the node. The next address field
contains the address of the next node in the list. This field is also referred as the forward link field.
It is an advanced form of a singly linked list, in which each node contains three fields namely,
 Previous address field
 Data field
 Next address field
Each node contains three parts:
1) An information field which contains the data.
2) A pointer field next which contains the location of the next node in the list.
 3) A pointer field prev which the location of the preceding node in list.
Advantage
 Deletion operation is easier.
 Finding the predecessor and successor of a node is easier.
Disadvantage
 More memory space is required, since it has two pointers.
The new node can then be inserted in the list at three different places namely
1. inserting as a first node in the list
2. inserting as a last node in the list
3. inserting an intermediate node in the list
1. INSERTING AS A FIRST NODE IN THE LIST:
 Get the new node using GETNODE ( ) and read the details of the node using
READNODE ( ).
 Check whether the list is empty or not .if the list is empty, assign new node as head. if
the list is not empty follow the next steps.
 The forward link field of the new field of the new node is made to point the first node in
the list by assigning the address of the first node.
 The backward link field of the first node is made to point the new node by assigning the
address of the new node.
 The assign the new node as the head pointer.

2. INSERTING AS A LAST NODE IN THE LAST:

 Get the new node using GETNODE( ) and read the details of the node using
READNODE ( ).
 Check whether the list is empty or not .if the list is empty ,assign new node as head . if
the list is not empty follow the next steps.
 The forward link field of the last node in the list is made to point the new node in the list
by assigning the address of the first node.
 The backward link field of the new node is made to point the last node by assigning the
address of the last node.
 The forward link field of the node is set to NULL.
3. INSERTING A INTERMIDIATE NODE IN THE LIST:
 Get the new node using GETNODE ( ) and read the details of the node using
READNODE ( ).
 Check whether the list is empty or not .if the list is empty, assign new node as head. if the
list is not empty follow the next steps.
 Get the address of the proceeding node after which the node is to be inserted.
 The forward link field of the new node is not to point the next node by assigning its
address.
 The backward link field of the new node is not to point the processing node by assigning
its address.
 The backward list of the next node is made point the new node by assigning its address.
 The forward link field of the preceding not is made to point the new node by assigning
the address in the new node.

DOUBLY LINKED LIST DELETION:

A node can be deleted from the list from three different places namely,
1. Deleting the first node from the list.
2. Deleting the last node from the list.
3. Deleting an intermediate node from the list.
DELETING THE FIRST NODE FROM THE LIST
1. Check whether the list is empty or not .if the list is not empty follows the next step.
2. Set the head pointer to the second node in the list.
3. Set the backward link field of the head node in the list to NULL.
4. Release the memory for the deleted node.
DELETING THE LAST NODE FROM THE LIST:
1. Check whether the list is empty or not. if the list is not empty follows the next step.
2. THE forward link field of the previous node is set to NULL. Release the memory for
the deleted node.
DELETING AN INTERMIDIATE NODE FROM THE LIST:
1. Check whether the list is empty or not. if the list is not empty follows the next step.
2. THE forward link field of the previous node is made to point the next node by
assigning its address.
3. The backward link field of the next node is made to point the previous made by assigning its
address.