Linked List

Linked list is a dynamic data structure that use memory dynamically. Link list may consists of several nodes according to requirements. Each node in link list holds data as well reference to other modes. This reference is used to perform various operations.Link list is best for better memory utilization.

Types of linked list

There are three types of link list in data structures.

1. Singly linked list
2. Doubly linked list
3. Circular linked list

Singly linked list

Singly linked list also known as singular or simple link list. In singly link list each node contain only one reference pointer and normally this is link to next node. It is suitable alternative of array. In singly link list only one way traversal is possible.

Singly link list use one pointer to track nodes in list. This pointer is normally known as head pointer.

Syntax of singly linked list

struct node {
int data;
node  *next;
};

We can also create node structure using class.

class node {
int data;
node next;
};

In node structure data type of data member may other than int such as float, char or double. There is no limitation on no of data items in node of link list, however in singly link list there will be single pointer.

Presentation of singly link list

Doubly Linked list

Doubly linked list contains two pointers, that are useful in forward and backward traversal. In doubly link list we can acees next and previous element for every node. Doubly linked list occupy more memory than singly link list.

Doubly linked list use two intial pointers to track the nodes in list. These two pointers are called head and tail pointers. If we want to traverse doubly link list in FIFO order in case of append insertion mode than we can use head pointer, and if we want to traverse list in LIFO order in caee of pre append mode than we can use tail pointer.

Syntax of Doubly linked list

Syntax for creating node in C++ using structure construct is as follow.

struct node {
int data;
node *next;
node *prev;
};

Node structure in doubly linked list using class is as follow.

class node {
int data;
node *next;
node *prev;
};

Presentation of Doubly linked list

Circular Linked list

Circular link list is much similar to singly link list except that the last node of list contain link to its first node. Normally last inserted node contain address of its head node.

Syntax of Circular linked list

Syntax of node in circular linked list is similar to the node structure in singly linked list.

Presentation of  Circular linked list

Uses of Linked list

Linked list can be used to implement dynamic data structures such as stack, queue, tree and graphs. When we use linked list for storage of data we can utilize memory more efficiently, because there is no need to define size of data set in prior.

Difference between Array and Linked List

Except that linked list and array can be used alternatively, there are some major difference between arrays and linked list.

Similarities of Array and Linked List

There are some common thing among arrays and linked list.

1. Array and linked list both are used to store and process the data.
2. Array and linked list provides sequential traversal of data set.
3. Array and linked list both can be used for implementation of other data structures such as stack and queue.