The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Linked List

A linked list is a data structure in which data is stored in structures called nodes and every node has a pointer to the next node in the list. A linked list can be visualised as a chain of nodes. A pointer usually termed as head points to the first node in the chain or list and using this head pointer, we traverse the entire list. Unlike arrays, linked List doesn't support random data access but insertion or deletion of data elements is very efficient. It just involves some pointer manipulation. We can recall that insertion or deletion of elements in arrays involve costly shifting operations which is very inefficient if the size of the array is very large. A node is dynamically created and inserted into the list when a new data element has to be created and it is deleted when an element has to be removed.

Types of Linked List
There are three different types of linked lists which are described below :
Single Linked List consists of nodes where each node contains a data element and a pointer which points to the next element in the list.
Double Linked List consists of nodes where each node contains a data element and a two pointers pointing to the previous and next element in the list.
Circular Linked List is a simple list in which last node points to the first node in the list.
Following diagram visualizes single and double linked lists :

linked list

We can optionally use a tail pointer which points to the last node of the list but it doesn't have real world use cases. Next, we would see some problems on linked list.

Back | Next

All problems on Linked List
* Insert, Delete and Search nodes in a single linked list
* Insert, Delete and Search nodes in a double linked list
* Sort a linked list where each node element is either 1 or 0
* Reverse a linked list in an efficient manner
* Merge two sorted linked lists
* Detect a loop in a given linked list