Linked List

Linked List as the name suggests, it's a linkage of Nodes which contain list.

What is Node?

In a simpler manner, Node can be thought as a box where we can put some items and it has glue on one side through which
another box can be connected. In CS terminology, it is a sequential group of nodes. Each node consists of its own data and the address of the next node and forms a chain.

Each node is separated into two different parts:

• The first part holds the information of the element or node(As depicted in the above fig.)
• The second piece contains the address of the next node (link / next-pointer field) in this structure list.

A linked list can be measured as a series of nodes where each node has at least one single pointer to the next connected node and in the case of the last node, a null pointer is used for representing that there will be no further nodes in the linked list.

In the data structure, you will be implementing the linked lists which always maintain head and tail pointers for inserting values at either the head or tail of the list is a constant time operation.

As such, linked lists in Data Structure Algorithm have the following characteristics:

1. Insertion is O(1)
2. Deletion is O(n)
3. Searching is O(n)




Out of the three operations, the one that stands out is that of insertion. In Data Structure Algorithm we chose to always maintain pointers (or more aptly references) to the node(s) at the head and tail of the linked list and so performing a traditional insertion to either the front or back of the linked list is an O(1) operation. An exception to this rule is performing an insertion before a node that is neither the head nor tail in a singly linked list. When the node we are inserting before is somewhere in the middle of the linked list (known as a random insertion) the complexity is O(n). In order to add before the designated node, we need to traverse the linked list to find that node’s current predecessor. This traversal yields an O(n) run time.

Types of Linked List

Following are the various types of linked list.

• Singly Linked List − Item navigation is forward only.
• Doubly Linked List − Items can be navigated forward and backward.
• Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

1.Singly Linked List:

In Simple Linked List,Each node that makes up a singly linked list consists of a value, and a reference to the next node (if any) in the list.

1.1 Insertion:

Adding a node to a singly linked list has only two cases:

1. head = ∅ in which case the node we are adding is now both the head and

tail of the list; or

2. we simply need to append our node onto the end of the list updating the

tail reference appropriately.

1) algorithm Add(value)

2) Pre: value is the value to add to the list

3) Post: value has been placed at the tail of the list

4) n ← node(value)

5) if head = ∅

6) head ← n

7) tail ← n

8) else

9) tail.Next ← n

10) tail ← n

11) end if

12) end Add

1.2 Searching:

Searching a linked list is straightforward: we simply traverse the list checking the value we are looking for with the value of each node in the linked list

Searching Algorithm:

1) algorithm Contains(head, value)
2) Pre: head is the head node in the list
3) value is the value to search for
4) Post: the item is either in the linked list, true; otherwise false
5) n ← head
6) while n 6= ∅ and n.Value 6= value
7) n ← n.Next
8) end while
9) if n = ∅
10) return false
11) end if
12) return true
13) end Contains

1.3 Deletion:

Deleting a node from a linked list is straightforward but there are a few cases

we need to account for:

1. the list is empty; or

2. the node to remove is the only node in the linked list; or

3. we are removing the head node; or

4. we are removing the tail node; or

5. the node to remove is somewhere in between the head and tail; or

6. the item to remove doesn’t exist in the linked list

The algorithm whose cases we have described will remove a node from anywhere within a list irrespective of whether the node is the head etc

1) algorithm Remove(head, value)

2) Pre: head is the head node in the list

3) value is the value to remove from the list

4) Post: value is removed from the list, true; otherwise false

5) if head = ∅

6) // case 1

7) return false

8) end if

9) n ← head

10) if n.Value = value

11) if head = tail

12) // case 2

13) head ← ∅

14) tail ← ∅

15) else

16) // case 3

17) head ← head.Next

18) end if

19) return true

20) end if

21) while n.Next 6= ∅ and n.Next.Value 6= value

22) n ← n.Next

23) end while

24) if n.Next 6= ∅

25) if n.Next = tail

26) // case 4

27) tail ← n

28) end if

29) // this is only case 5 if the conditional on line 25 was f alse

30) n.Next ← n.Next.Next

31) return true

32) end if

33) // case 6

34) return false

35) end Remove

1.4 Traversing:

You start at the head of the list and continue until you come across a node that is ∅. The two cases are as follows:

1. node = ∅, we have exhausted all nodes in the linked list; or

2. we must update the node reference to be node.Next.

Algorithm:

1) algorithm Traverse(head)

2) Pre: head is the head node in the list

3) Post: the items in the list have been traversed

4) n ← head

5) while n 6= 0

6) yield n.Value

7) n ← n.Next

8) end while

9) end Traverse

2.Doubly Linked List:

Doubly linked lists are very similar to singly linked lists. The only difference is that each node has a reference to both the next and previous nodes in the list.

Note#Searching and traversal Algorithm for double linked list is same as single linked list

2.1 Insertion

The only major difference between the algorithm in given below wrt to an algorithm for the single linked list  is that we need to remember to bind the previous pointer of n to the previous tail node if n was not the first node to be inserted into the list.

1) algorithm Add(value)

2) Pre: value is the value to add to the list

3) Post: value has been placed at the tail of the list

4) n ← node(value)

5) if head = ∅

6) head ← n

7) tail ← n

8) else

9) n.Previous ← tail

10) tail.Next ← n

11) tail ← n

12) end if

13) end Add

2.2 Deletion:

Deletion for DLL is also the same as SLL but only difference here is we have to add task of binding an additional reference (Previous) to the correct value.

Algorithm:

1) algorithm Remove(head, value)
2) Pre: head is the head node in the list
3) value is the value to remove from the list
4) Post: value is removed from the list, true; otherwise false
5) if head = ∅
6) return false
7) end if
8) if value = head.Value
9) if head = tail
10) head ← ∅
11) tail ← ∅
12) else
13) head ← head.Next
14) head.Previous ← ∅
15) end if
16) return true
17) end if
18) n ← head.Next
19) while n 6= ∅ and value 6= n.Value
20) n ← n.Next
21) end while
22) if n = tail
23) tail ← tail.Previous
24) tail.Next ← ∅
25) return true
26) else if n 6= ∅
27) n.Previous.Next ← n.Next
28) n.Next.Previous ← n.Previous
29) return true
30) end if
31) return false
32) end Remove

3. Circular Linked List

In the circular linked list the last node of the list contains the address of the first node and forms a circular chain.

Advantage of linked List:

• They are a dynamic in nature which allocates the memory when required.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.

Disadvantages of Linked Lists:

• The memory is wasted as pointers require extra memory for storage.
• No element can be accessed randomly; it has to access each node sequentially.
• Reverse Traversing is difficult in linked list.

Applications of Linked Lists:

• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list.
• In Linked Lists we don't need to know the size in advance.

Codes(Only Functions):

Insertion:

void insertFirst(int key, int data) {

   //create a link

   struct node *link = (struct node*) malloc(sizeof(struct node));

   link->key = key;

   link->data= data;

   if (isEmpty()) {

      head = link;

      head->next = head;

   } else {

      //point it to old first node

      link->next = head;

      //point first to new first node

      head = link;

   }   

}

Deletion Operation

//delete first item

struct node * deleteFirst() {

   //save reference to first link

   struct node *tempLink = head;

   if(head->next == head) {  

      head = NULL;

      return tempLink;

   }     

   //mark next to first link as first 

   head = head->next;

   //return the deleted link

   return tempLink;

}

Display List Operation

//insert link at the first location

//display the list

void printList() {

   struct node *ptr = head;

   printf("\n[ ");

   //start from the beginning

   if(head != NULL) {

      while(ptr->next != ptr) {     

         printf("(%d,%d) ",ptr->key,ptr->data);

         ptr = ptr->next;

      }

   }

   printf(" ]");

}

   //start from the beginning

   if(head != NULL) {

      while(ptr->next != ptr) {     

         printf("(%d,%d) ",ptr->key,ptr->data);

         ptr = ptr->next;

      }

   }

   printf(" ]");