Linked List

Linked List vs Array

Array :

·        Linear collection of data elements

·        Store value in consecutive memory locations

·        Can be random in accessing of data

Linked List :

·        Linear collection of nodes

·        Doesn’t store its nodes in consecutive memory locations

·        Can be accessed only in a sequential manner

Single Linked List

is a linked list which node contain only a single link to other node

To create a linked list, we need to define a node structure

Insert

To insert a new value, first we should dynamically allocate a new node and assign the value to it and then connect it with the existing linked list.

·        In front of the head

Delete

To delete a value, first we should find the location of node which store the value we want to delete, remove it, and connect the remaining linked list.

There are two conditions we should pay attention to:

·        if x is in a head node or

·        if x is not in a head node.

Circular Linked List

In circular, last node contains a pointer to the first node

We can have a circular singly linked list as well as a circular doubly linked list.

There is no storing of NULL values in the list

Doubly Linked List or Two-Way Linked List

Two-way linked list is a linked list data structure with two link, one that contain reference to the next data and one that contain reference to the previous data.

Insert

We should allocate the new node and assign the value to it, and then we connect the node with the existing linked list.

Delete

There are 4 conditions we should pay attention when deleting:

·        The node to be deleted is the only node in linked list.

·        The node to be deleted is head.

·        The node to be deleted is tail.

·        The node to be deleted is not head or tail.

Circular Doubly Linked List

It is similar with circular single linked list, but total pointer in each node here is 2 (two) pointers.

Header Linked List

A header linked list is a special type of linked list which contains a header node at the beginning of the list.

So, in a header linked list, START (L) will not point to the first node of the list but START (L) will contain the address of the header node.