How does linked list work?

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after the array.

Linked lists are made up of nodes, where each node contains a reference to the next node in the list. In addition, each node contains a unit of data called the cargo. A linked list is considered a recursive data structure because it has a recursive definition. A linked list is either the empty list, represented by None, or a node that contains a cargo object and a reference to a linked list.

Types of Linked Lists

There are different implementations of Linked List available. Those are-

• Singly Linked List - Singly Linked Lists are a type of data structure. In a singly linked list, each node in the list stores the contents and a pointer or reference to the next node in the list.

• Doubly Linked List - Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List.

• Circular Linked List - In circular linked list the last node of the list holds the address of the first node hence forming a circular chain. The implementation of a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that in circular linked list the last Node will have its next point to the Head of the List. In Linear linked list the last Node simply holds NULL in its next pointer.

Application of Linked List

• Linked lists are used to implement stacks, queues, graphs, etc.

• Linked lists let you insert elements at the beginning and end of the list.

• In Linked Lists, we don't need to know the size in advance.

• The real-life application where the linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.

• Another example can be Multiplayer games. All the Players are kept in a Linked List and the pointer keeps on moving forward as a player's chance ends.

• Linked List can also be used to create Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, whereas in Linked List, only one pointer is required.

A linked list includes the following methods -

Insert

This insert method takes data, initializes a new node with the given data, and adds it to the list. Technically you can insert a node anywhere in the list, but the simplest way to do it is to place it at the head of the list and point the new node at the old head. The time complexity of insert is constant O(1). This method will always take the same amount of time. It can only take one data point, it can only ever create one node, and the new node doesn’t need to interact with all the other nodes in the list, the inserted node will only ever interact with the head.

Size

The size method is very simple, it basically counts nodes until it can’t find anymore, and returns how many nodes it found. The method starts at the head node, travels down the line of nodes until it reaches the end while keeping track of how many nodes it has seen. The time complexity of size is O(n) because each time the method is called it will always visit every node in the list but only interact with them once, so n * 1 operations.

Search

Search is actually very similar to size, but instead of traversing the whole list of nodes it checks at each stop to see whether the current node has the requested data and if so, returns the node holding that data. If the method goes through the entire list but still hasn’t found the data, it raises a value error and notifies the user that the data is not on the list. The time complexity of search is O(n) in the worst case. You often hear about best case / average case / worst case for Big O analysis.

Delete

Delete is very similar to search. The delete method traverses the list in the same way that search does, but in addition to keeping track of the current node, the delete method also remembers the last node is visited. When delete finally arrives at the node it wants to delete, it simply removes that node from the chain by leapfrogging it. Means that when the delete method reaches the node it wants to delete, it looks at the last node it visited that is the previous node and resets that previous node’s pointer so that, rather than pointing to the soon-to-be-deleted node, it will point to the next node in line. Since no nodes are pointing to the poor node that is being deleted, it is effectively removed from the list. The time complexity for delete is also O(n) because in the worst case it will visit every node, interacting with each node a fixed number of times.

Let's look how Linked list work -

Linked list can be visualized as a chain of nodes, where every node points to the next node. We shall learn this here -

• First, create a node using the same structure and find the location where it has to be inserted.

• Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C.

• Now, the next node at the left should point to the new node. This will put the new node in the middle of the two.

• Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

• Next in deletion, first, locate the target node to be removed, by using searching algorithms.

• Then the left (previous) node of the target node now should point to the next node of the target node.

• This will remove the link that was pointing to the target node. Now, using the code - TargetNode.next −> NULL; we will remove what the target node is pointing at.

• We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.

• Then we need to make the last node to be pointed by the head node and reverse the whole linked list.

• We traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node. Remember, we have to make sure that the last node is not the lost node. So we'll have some temp node, which looks like the head node pointing to the last node.

• Now, we shall make all left side nodes point to their previous nodes one by one.

• Except for the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.

• We'll make the head node point to the new first node by using the temp node.

• The linked list is now reversed.

Why you use linked lists?

Linked list is often compared to arrays. Whereas an array is a fixed size of sequence, a linked list can have its elements to be dynamically allocated.

A linked list saves memory. It only allocates the memory required for values to be stored. In arrays, you have to set an array size before filling it with values, which can potentially waste memory. Its nodes can live anywhere in the memory. Whereas an array requires a sequence of memory to be initiated, as long as the references are updated, each linked list node can be flexibly moved to a different address.

Apart from its internal representation, the working of a linked list is not much different from the other list classes. The power of the linked list lies in its core representation. Though inserting elements at the beginning and end of the list offers a significant performance improvement, the disadvantage of slow insertion and deletion at the middle of the list outweighs them. Overall sees, It's particularly advantaged to use it in a situation where there are a voluminous addition and deletion of elements at the beginning and at the end of the list.