A Linked List is a collection of elements linked together. Each element in a linked list is called a Node. Each Node has a reference to the next node apart from the data that it holds. Usually the first node is called Head and last node is called Tail.
Linked List ADT
The data, link and the following operations make linked list an ADT:
- Count (or length)
The Linked List Node
A simple linked list node can be shown as:
In real world you will have complex data or may use a generic type for data, if the programming language support it (e.g. generics in Java).
SINGLY LINKED LISTS
Each element will have a pointer (or link) to the next element in the list. The link of the last node will be null, which indicates end of the list.
Steps for traversing the linked list (and printing the element data)
- Follow the pointers.
- Display the contents of the nodes.
- Stop when next pointer points to null.
Note: To count the number of elements, you can use a counter variable and incrementing it while traversing.
INSERTION INTO A SINGLY LINKED LIST
We can insert an element either at the beginning, at the end or in middle.
Steps for inserting at the beginning
- Update the next pointer of the new node to the current head.
- Update the head pointer to point to the new node.
Steps for inserting at the end
- New node’s next pointer is set to null.
- Traverse till the last node if we are not using a tail pointer.
- Last node’s next pointer points to the new node.
Steps for inserting at middle (nth location)
- Traverse till (n-1)th location and assign it as position.
- Now nodes next pointer points to positions next pointer.
- Position nodes next pointer points to new node.
- Need to check that the location n is not greater than size+1.
- This will also work even if n is added to the end, but will have to adjust tail (if available) accordingly.
- Insertion at the end and inserting at arbitrary location are common list operations.
Deleting first node
- Create a temporary node that point to head
- Make the head points to point to next node
- Dispose (and return) temp node
Deleting the last node
- Traverse the list and while traversing maintain previous node as well.
- Update the previous nodes next to null.
- Dispose the tail node.
Deleting an intermediate node
- Traverse the list maintaining a previous node as well.
- Change the previous nodes next pointer to the next node of the node to be deleted.
- Dispose the current node to be deleted.
The deletion of last node and intermediate node can be combined by changing previous nodes next pointer to node-to-be-deleted’s next. If current is the last element assigning its next to previous next means assigning null to previous next. We can do this deletion without using a separate previous pointer.
DOUBLY LINKED LIST
Doubly linked list is a linked list which has two links: one that point to the previous element and one that point to the next element.