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,   

There are different types of linked lists that are formatted by changing the link position. They are,

• Singly-linked list
• Double linked list
• Circular linked list

Difference between the linked list and an array

Array	Linked list
An array is the organizing of fixed-sized similar elements in the contiguous memory location. In arrays, the number of elements is fixed and does not change. Elements of an array are stored in contiguous or adjacent memory locations. Arrays are easier to maintain than a linked list.	A linked list is a linear data structure used to store similar data in memory. The number of data items stored in a linked list varies. Elements in a linked list are stored anywhere in memory, and the order of elements is maintained by links between them. Linked lists are difficult to maintain.

Singly Linked List

A singly linked list is a list in which each node is linked with others. A node is a structure element containing data and link field.

 

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

• Traversal
• Insertion
• Deletion

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 != NULL repeat 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]
• return

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

[quote] temp=temp -> link[traversing the list up to ith position]

                                     [repeat step 6 until i=loc-1]

new -> link=templink

temp -> link=new[inserting the node at the specified location]

[/quote]

• return

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=NULL [list is empty] print “list is empty” deletion not possible return
• Step 2: else

[quote]

               FIRST=FIRSTlink[making the FIRST pointer to point to the second node]

              [logically deleting the first node]

[/quote]

• 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=templink[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 templink!=NULL, repeat step 4[traverse the list up to last but one node]
• Step 4: temp=templink
• Step 5: templink=NULL[logically deleting the last node]
• Step 6: return