A linked list is a linear collection of data items where each item points to a next item. Unlike an array, the items in the linked list do not need to be in a continuous memory location. They can be anywhere in the memory as long as they are connected by a link. Figure 1 shows an example of a linked list having 4 items.
Each item in a linked list is called a Node. A node has two parts: the first part is called
data and it holds the actual value of the item and the second part is called
next and it holds the address of the next node in the sequence. Using the
next part of the node, we can get to the next item in the linked list. The first item in the list is pointed by a pointer called
head. We can get to the second item by simply using the
next part of the
head. We can get to the third item using the
next part of the second node and so on. The last item points to nowhere. In this way, if we know the pointer to the first item in the list, we can get to any item in the list in linear time.
Depending upon how one item is linked with another item in the list, a linked list can be divided into many types. Some of the types of the linked list are given below.
- Singly Linked List: This type of linked list has only one pointer that points to the next item in the list. That means we can only go in the forward direction. The list given in Figure 1 is an example of a singly linked list.
- Doubly Linked List: It has a pointer to the next node in the list as well as a pointer to the previous node in the list. That means we can go in both forward and backward direction. Figure 2 shows an example of a doubly linked list.
- Circular Linked List: In a linear linked list, the last item points to nowhere. That means we can not go further in the forward direction from the last node. In a circular linked list, however, the last node points to the first node of the list making it a circular structure. Figure 3 is an example of a circular singly linked list.
An item can be inserted (or deleted) at the front of the linked list (singly or doubly) in constant time O(1). This operation costs a linear time in arrays.
Linked lists are widely used in many applications. Some of them are listed here.
- It used in other data structures like Stack, Queue, Graph, Tree, etc.
- It can be used to create a music playlist or photo viewer where we can go to next, previous, first or last item easily.
- It is used to make an Undo feature in many applications where the states are nodes of the list.
- It is used in operating system process management where the process descriptors (pd) are the nodes of the list.
- It can be used to make the symbol tables in a compiler.
- and much more…