Linked List Data Structure
A linked list is a linear data structure used to stores similar data in memory. The elements in the linked list are not stored in adjacent memory locations but are stored randomly. The linked list is a collection of elements known as nodes which contains two fields of information. One contains the data items and the other contains the link or address of the successor list element. A node can be represented as,
- Singly-linked list
- Double linked list
- Circular linked list
Difference between the linked list and an array
Singly Linked List
What is Node?
The node in the list need not be stored in the contiguous memory location. A node can contain any number of data fields but only one link field.
Advantage Of Single Linked List
- The singly linked list is simple to implement compared to a circular and doubly linked list.
Disadvantages Of Single Linked List
- If the address of the first node is lost, then the linked list can’t be accessed.
- For deletion operation, in addition to the address X of the node to be deleted we also need the address of the first node to reach predecessor of X. So it is not efficient to perform deletion operation.
Suppose we want to delete an element at the position i, we need the node at position (i-1) to link to (i+1) node. This can only be obtained by traversal from the first addressed node to (i-1) position.
- Every node is not accessible by its successor. A linked list can be traversal only in one direction.
- In the above diagram of a singly linked list, the address of the 3rd node is stored in the link field of the second node, address of the second node is stored in the link field of the first node and the address of the first node is stored in a pointer called as root. This pointer is not a part of the list rather list holds the value NULL in its link field, indicating the end of the list.
Basics Operations on the Singly Linked List
Single Lined list traversal
The singly linked list can be traversed in the direction from the first node to the last node using the pointer root or head or FIRST.
Algorithm: Traversal (FIRST)
- Step 1: temp=FIRST [ temp is a temporary pointer for traversing the tree]
- Step 2: Till
temp -> link != NULLrepeat through step 3.
- Step 3:
temp=temp -> link
- Step 4: return
Single Lined list Insertion
The insertion of a node into a singly linked list can be at different locations i.e., at beginning of list at a specified location in the list, or at the end of the list.
Insertion of the node at the Beginning of list
To inserts a node at the beginning. Make the link field of new node point to the first node and make the FIRST pointer to point to the new node.
Algorithm: insert at the beginning (element, FIRST)
- Step 1: create a new node ( i.e. allocate memory, returning a pointer ‘new’)
- Step 2: new -> data=element[insert data into node created]
- Step 3: new – > link=FIRST[New node pointer to the first node]
- Step 4: FIRST=new[FIRST pointer pointing to new node]
Insertion of node at the Specified Position
To insert a new node between the ith and (i+1)th node, the list should be initially traversed up to ith node, then the link field of ith node should be made to point to a new node and the link field of the new node is made to point to (i+1)th node.
Algorithm: insert at a specified location (element, FIRST, loc)
- Step 1: create a new node
- Step 2: new -> data=element
- Step 3: temp=FIRST[temp is a temporary pointer for traversing the list]
- Step 4: if loc=1 then call insert at the beginning(FIRST)
- Step 5: if loc=n+1 then call insert at ending(FIRST)
- Step 6: otherwise for i=1 to i=loc-1
temp=temp -> link[traversing the list up to ith position]
[repeat step 6 until i=loc-1]
new -> link=templink
temp -> link=new[inserting the node at the specified location]
Insert of node at the End of List
To insert a node at the end of the singly linked list traverse the list up to the last node, then make the link of the last node point to a new node. Make the link field of new node point to NULL.
Algorithm: insert at the end (element, FIRST)
- Step 1: create a new node
- Step 2: new -> link=NULL
- Step 3: new -> data=element
- Step 4: temp=FIRST
- Step 5: until temp!=NULL repeat step 6
- Step 6: temp=temp -> link[traversing]
- Step 7: temp -> link=new[inserting node at end]
- Step 8: return
Single Lined list Deletion
A node can be deleted from the singly linked list in two ways, i.e., logically, physically. In logical deletion, the node is no more present in the list (i.e., reference to the node is broken) but physically present in the memory. But, in physical deletion of the node, the node is permanently deleted by deallocating (free) the memory allocated to the node.
The deletion of a node at different locations in the list, i.e., in the beginning, at the specified location, at the end can be implemented through the following algorithms.
Deletion of node at the Beginning
Algorithm: delete at the Beginning (FIRST)
- Step 1: if FIRST=NULLprint “list is empty” deletion not possible return
- Step 2: else
FIRST=FIRSTlink[making the FIRST pointer to point to the second node]
[logically deleting the first node]
- Step 3: return
- Deletion of Node at Specified Location
- In order to delete ith node, we have to traverse the list upto (i+1)th node.
- Step 1: declare a variable i=1 and a pointer variable temp
- Step 2: check, if FIRST=NULL, then print “deletion not possible” return
- Step 3: assign temp=FIRST[temp is a pointer for traversing]
- Step 4: check if loc==1 [if the node to be deleted is the first node] then, call delete at the beginning(FIRST) else, if loc==n[if the node to be deleted is the last node] then, call delete at the end(FIRST)
- Step 5: check, if (loc>1 and loc<n) then, until i<loc-1 go through step 6 and step 7.
- Step 6: increment I by 1
- Step 7: temp=templink[traversing the list]
- Step 8: temp -> link=NULL [logically deleting the specified node]
- Step 9: return
Deletion of node at End
To delete a node at the end, traverse the list up to last but one node and store and store NULL in its link field.
Algorithm: delete at the end (FIRST)
- Step 1: if FIRST =NULL print “deletion not possible, list empty” return
- Step 2: temp=FIRST [temp is temporary pointer]
- Step 3: until templink!=NULL, repeat step 4[traverse the list up to last but one node]
- Step 4: temp=templink
- Step 5: templink=NULL[logically deleting the last node]
- Step 6: return