Data Structure - Linked List

Data structures give order to the abstract world of code (software). There are many types of data structure. Among them linked list is the most fundamental type of data structure. Using one or another form of linked list, other data structures (queues or stacks for example) can be created.

Let us look at the theory behind linked list. I promise to try and make it interesting.

The basic unit of a linked list is what is called a node. A node is something like a Lego brick, many of which you can combine to create something. As with the Lego brick, there are different types of nodes, but the most basic form contains a data element and a reference element.

• Data Element - As the name suggests, the data element holds the data. It can be anything from simple data like numbers or characters, to complex data like a record holding the details of a song in a music album.
• Reference Element - Reference element is of the node can either be empty or be containing the information of where the next node of the list is present. When implemented in machine code, it has the address within the memory where the next node is residing.

A linked list is nothing but a set of nodes where the reference element points to the next node of the list. The last node has its reference element empty. If a list is supposed to hold the details of all songs in a particular album, the number of nodes will be equal to the number of songs. The first node will contain the details of the first song, and the reference will be pointing to the next node containing details of the second song. And this goes on until we reach the last node.

Designing the nodes in different fashion and setting up the linked list in a particular way, we can get many different configurations of the linked list.

• Singly-linked list - This is what we have seen. There will be a stream of nodes, one having reference to the next; it will have a start node and an end node.
• Doubly-linked list - This is again a list of nodes, but the nodes are a variant of what we have seen. The node will have two reference elements instead of one. These references point to the next and the previous nodes
• Circular linked list - This is a interesting configuration of the linked list. This list does not have end points. If a list is taken and the end node's reference is made to point to the first node, it becomes a circular linked list.

As mentioned earlier, these linked lists can be configured to form other specific type of data structures. It depends on how nodes are added and removed from the list. Operations to add and remove nodes to the list are defined in a particular way. It can actually be done in several ways, but by putting a constraint on how these operations are done, the linked list morph into other data structures.