An Intro to the Linked List
Data structures and algorithms are the foundations to programming. It has become a norm for every interviewer to test on these basics as they provide techniques for handling data efficiently. A programmer without an understanding of these techniques may build an inefficient solution or take a longer time to resolve the problem. This article introduces you to one of the commonly used linear data structures called Linked Lists.
Linear Data Structure
A data structure is a container that stores data in a specific layout which allows for efficient access and modification. A data structure can either be linear or non-linear. While a linear data structure has elements arranged sequentially, a non-linear structure contains elements in a hierarchical order.
Linear Data Structure Characteristics
- Data Element Arrangement: Sequential
- Levels: All data elements are present at a single level
- Traversal: Can be traversed completely in a single run
- Implementation Complexity: Easier to implement
- Memory Utilization: Inefficient
- Time Complexity: Increases with increase in size
Linked List
A linked list is a collection of elements called nodes arranged in a linear fashion. Each node contains a data field and a pointer to the succeeding node in the list called next. The first and last node of a linked list usually are called the head and tail of the list. The head pointer points to the first node and the last node will point to a null value. Note that the head is not a separate node but a reference to the first node. When the list is empty, the head pointer points to null.
Linked lists are dynamic and flexible and can expand and contract in size. Memory for linked lists is allocated during execution or runtime.
Types Of Linked List
- Singly Linked List: Being unidirectional in nature, the node traversal can be done in the forward direction only (see pic above).
- Doubly Linked List: Being bi-directional, the node traversal can be done in both forward and backward directions. Each node has an additional pointer called prev, pointing to the previous node.
- Circular Linked List: A variation of linked list in which the last element is linked to the first element forming a circular loop. It can take either of the above two forms. In a circular doubly linked list, the prev pointer of the head points to the tail and the next pointer of the tail points to the head.
Linked List Operations
- Searching: To find the first element with the given value in the linked list by a simple linear search and return a pointer to this element.
- Insertion: To insert an element ‘x’ into the linked list is a multi-step process. An insertion can be done in 3 different ways: insert at the beginning of the list, insert at the end of the list and insert in the middle of the list.
- Deletion: To remove an element ‘x’ from the linked list is a multi-step process. A deletion can be done in 3 different ways: delete from the beginning of the list, delete from the end of the list and delete from the middle of the list.
- Traversal: To traverse all the nodes one after another.
- Updating: To update a given node.
- Sorting: To arrange nodes in a linked list in a specific order.
- Merging: To merge two linked lists into one.
Node Insertion
Shown below is an insert operation to the middle of a singly linked list:
Node Deletion
Shown below is a delete operation from the middle of a singly linked list:
Time Complexity
- A linked list is accessed via its head node. One has to only traverse through each node to reach the target node. Thus access is O(n).
- Searching for a given value in a linked list similarly requires traversing all the elements until you find that value. Thus search is O(n).
- Inserting into a linked list requires re-pointing the previous node to the inserted node, and pointing the newly-inserted node to the next node. Thus insertion is O(1).
- Deleting from a linked list requires re-pointing the previous node (the node before the deleted node) to the next node (the node after the deleted node). Thus deletion is O(1).
Advantages
- Ease of insertion and deletion which takes O(1) time
- Less memory wastage due to dynamic memory allocation
Disadvantages
- Random access is not allowed
- Requires extra memory space to store a reference to the next node
Applications
- Implementation of stacks, queues and graphs and in areas that require dynamic memory allocation
- Used for symbol table management in compiler design
- Used in switching between programs using Alt + Tab (implemented using Circular Linked List)
- Manipulation of polynomials by storing constants in the node of linked list
- Used in music player where the songs are linked to previous & next songs
- Used by browsers to implement backward and forward navigation of visited web pages i.e. back and forward button
- Many modern operating systems use doubly linked lists to maintain reference to active processes, threads and other dynamic objects
Wrap Up
While linked lists have their own share of pros and cons, they are still widely used today in most data structures and applications. Being a foundational topic, it is important for every developer to have an understanding of this linear data structure. I hope this article is helpful in meeting its objective. Feel free to share your views in the comments section below.
References:
Common Data Structures every programmer should know
