Categories: Computers & Internet

Linked Lists – Data Structures and Algorithms

Linked lists can be thought of from a high level perspective as being a series of nodes. Each node has at least a single pointer to the next node, and in the last node’s case a null pointer representing that there are no more nodes in the

linked list.

In DSA our implementations of linked lists always maintain head and tail pointers so that insertion at either the head or tail of the list is a constant time operation. Random insertion is excluded from this and will be a linear operation. As such, linked lists in DSA have the following characteristics:

Insertion is O(1)
2. Deletion is O(n)
3. Searching is O(n)

Out of the three operations the one that stands out is that of insertion. In DSA we chose to always maintain pointers (or more aptly references) to the node(s) at the head and tail of the linked list and so performing a traditional insertion to either the front or back of the linked list is an O(1) operation. An exception to this rule is performing an insertion before a node that is neither the head nor tail in a singly linked list. When the node we are inserting before is somewhere in the middle of the linked list (known as random insertion) the complexity is O(n). In order to add before the designated node we need to traverse the linked list to ¯nd that node’s current predecessor. This traversal yields an O(n) run time.

Related Post

This data structure is trivial, but linked lists have a few key points which at times make them very attractive:
1. the list is dynamically resized, thus it incurs no copy penalty like an array or vector would eventually incur; and
2. insertion is O(1).

Singly Linked List

Singly linked lists are one of the most primitive data structures you will ¯nd in this book. Each node that makes up a singly linked list consists of a value, and a reference to the next node (if any) in the list.




  • Khushal Sharma

    Recent Posts

    Heart Attack Causes and its Solution

    What is the Main Cause of a Heart Attack? What is its Solution? A heart attack is the blockage of… Read More

    4 months ago

    Understanding the Debt Ceiling: Its Impact, Importance, and Implications

    In the vast economic arena, one term that often takes center stage, inciting extensive debates and discussions, is the "debt… Read More

    9 months ago

    De-Dollarization: The New World Order of Currency and Its Global Impact

    De-Dollarization: The Changing Face of Global Finance The financial landscape is in a state of flux, with an intriguing economic… Read More

    10 months ago

    Unstoppable Bayern Munich: The Story Behind Their 11th Consecutive Bundesliga Title

    The curtains closed on a dramatic Bundesliga season with Bayern Munich standing tall once again, clinching their 11th straight title.… Read More

    10 months ago

    Celine Dion Cancels Concert Tour Due to Deteriorating Stiff-Person Syndrome

    The Unfolding Story of Celine Dion's Health In recent news that has left fans across the globe stunned, iconic singer… Read More

    10 months ago

    Navigating the Crossroads: LeBron James, Anthony Davis, and the LA Lakers’ Uncertain Future

    As the echoes of the recent NBA season start to fade, the attention of enthusiasts is firmly glued to one… Read More

    10 months ago