Linked List (Data Structure)
Linked list is a dynamic data structure whose memory is allocated dyamically. It provides constant time complexity when it comes to insertion or deletion of element at any position. It is the second most used data structure after arrays.
Linked list is a linear data structure, meaning that one data point follows another. It's a list of values that could be stored at non-contiguous locations in memory, called nodes, connected by links. Each node contains data and a pointer to the next node. Unlike arrays, linked lists don't allow random access. All access is sequential.
Just as a train has coaches connected in a sequence, so are the nodes connected linearly in a linked list.
What are the terms associated with linked lists?
Some terms related to the linked list are as follows:
- Node: a record in a linked list that contains a data field and a reference, a self-referential structure.
nextpointer: the field of a node that contains a reference to the next node.
prevpointer: the field of the node that contains a reference to the previous node.
- Head Node: the first node of the linked list.
- Tail Node: the last node of the linked list.
What are the different types of linked lists?
Singly-Linked List consists of nodes, starting from head node to
NULL, where each node contains a data field and a
Doubly-Linked List consists of nodes, where each node contains a data field, a
nextpointer and a
Circular Linked List is similar to a singly-linked list except that the last node instead of connecting to
NULLconnects to the first node, creating a ring.
Circular Doubly-Linked List is a mixture of the circular and doubly-linked list which has two pointers
next, and the last node connects to the first node.
Multi-Linked List consists of nodes, where each node contains a data field and two or more pointers. A doubly-linked list is a special case of the multi-linked list, which has two pointers that are the exact inverse of each other. These lists are typically used to implement different sorting of the nodes. For example, given student names and their marks, one set of pointers will sort by name and the other set by marks.
What's the time and space complexity of linked list operations?
The basic linked list operations with their associated complexity are as follows:
- Access / Search: Access is via the head node and additionally the tail node in case of doubly-linked list. There's no random access like in arrays. Access in the worst case requires O(n) time. Presence of the head pointer and the tail pointer makes access of first and last node in O(1) time.
- Insert: First we need to reach the position at which the node has to be inserted is to be performed. The worst-case time complexity of insertion of a node into a linked list is O(1).
- Delete: First we need to reach the node that needs to be deleted. The worst-case time complexity of deletion of a node from a linked list is O(1).
How do insertions and deletions in linked lists work?
For insertions, we need to create a node, assign its value, insert it at the required position while updating the relevant pointers. For inserting node at the start, we need to link it to the current head node and then update the head pointer to the newly inserted node. For inserting node in the middle, we need to update the next pointer of previous node and next pointer of the inserted node. For inserting node at end, we have to traverse the whole linked list till we find the last node and then link it to newly created node.
For deletions, we first need to know the location of the node. For deleting node from the start, we need to head pointers to the next pointer of the first node. For deleting node in the middle, we need to link its previous node to its next node. For deleting a node at the end, we update the next pointer of the second-last node to
The above procedures have to be enhanced for doubly-linked lists and circular linked lists.
What are sentinel nodes in linked lists?
Implementations of linked lists need to handle the special case when the list is empty. Head and tail pointers will be null in an empty list. These need to be handled specially in code. This complicates code and raises the possibility of bugs. To solve this problem, sentinel nodes are used.
Sentinel nodes are nodes at the ends of linked list and don't contain data. An empty doubly-linked list will have two sentinel nodes, called header node at the start and trailer node at the end. Head and tail pointers will point to these sentinel nodes.
In a singly-linked list, only the header node will be present. Sometimes the term Header Linked List is used for such a list. The last node's next pointer could be null or point to the header node.
Though sentinel nodes simplify code, they take up extra space. This may be an issue if the application uses many short lists.
What other data structures can be implemented using linked lists?
Linked list, being a linear data structure, can be used to implement other linear data structures. In particular, linked list is a concrete data type. Stacks and queues, which are abstract data types, can be implemented in linked lists. A singly-linked list suffices for a stack (LIFO operation) whereas a doubly-linked list in needed for a queue (FIFO operation).
Tree and graphs are non-linear data structures. These can be implemented with linked list that need to be customized for non-linear storage. Algorithms that operate on these will also be different. For example, a node in a binary tree will have one parent and at most two children. A doubly-linked list node can be modified for this purpose: instead of
prevpointers we have
rightpointers to link to the child nodes. Note that with this structure, we can get to the children from a parent but not vice versa.
Any arbitrary non-linear storage (n-ary trees or graphs) can be implemented by introducing more pointers into each node of the linked list.
How are linked lists implemented in various programming languages?
Most of the languages have built-in singly-linked lists, some have ADTs or templates to build linked lists.
C++ has a
std::listcontainer to implement linked lists. It is a doubly-linked list with a head node.
Java has the
LinkedListclass that implements the
Listinterface. It's a doubly-linked list.
Python does not have a built-in linked list. Python's
listis a dynamic array.
C# also has
LinkedListas Java which is a doubly-linked list implementation.
What are the different storage mechanisms for linked lists?
There are two ways to store node data: internal and external. Internal storage stores data within the node. External storage stores data elsewhere and only a reference to that data is stored within the node.
Internal storage is more cache-friendly, uses less metadata and simplifies memory management. External storage needs more memory to store the reference to the data. Getting to the data requires dereferencing. Otherwise, external storage is more generic since any type or size of data can be stored. Same data can be referenced from multiple linked lists. Linked lists with external storage can also be more easily adapted to new requirements.
How do arrays and linked lists compare in terms of performance?
Array is a linear data structure by way of storing values in contiguous locations. Linked list is a linear by way of storing reference along with value. Array has better locality of reference than linked list and its memory access is predictable than that of linked list. Linked list utilises memory efficiently as it occupies non-contiguous locations limited only by system memory whereas dynamic array requires contiguous space and needs to be resized. .
Array offers random access in O(1) time whereas linked list offers sequential access in O(n) time. When it comes to insertion and deletion of data, linked list is quite flexible and does it in constant O(1) time. However, if insertion or deletion require first searching for the element, the operations become O(n). Insertions and deletions in an array require O(n) at worst if elements need to be shifted.
Linked list occupies more memory as compared to array because each node stores references to its next node.
How do I optimize linked lists for performance?
System performance is often limited by memory access times and not CPU speeds. Performance is generally improved using data caches and pre-fetching data into the cache. Since elements of a linked list are often stored in different memory locations, caching and pre-fetching aren't effective.
However, it's possible to improve performance by implementing custom memory management. For example, C++ STL allows use of a custom allocation with
forward_list. Same allocator is used for all lists of a type, which is fine if there are many small lists to manage. Otherwise, we would need to implement custom linked list with allocator for each instance. One approach is to implement linked list using STL's
vector. This can be improved with a compact operation to make the list more cache-friendly.
Unrolled linked list is also cache-friendly. Multiple data elements are stored sequentially in a single node.
For faster searches, skip list maintains layers of pointers, each layer skipping some elements. Where data filtering is a common operation, an STL
vectorbacked by a bitset is one solution.
What are some real-world application of linked lists?
A singly-linked list is used when a user views all the images from the gallery as a slideshow. Collision techniques use a singly-linked list to store all the data items in chains that map to the same value in a hash table. It can be used to keep a track of the user's webpage history.
A doubly-linked list is used to implement the undo-redo function in any editor. It is used to implement the next and prev buttons while a user is browsing and wants to visit already visited web pages. A music player also uses a doubly-linked list to store the next and previous track and a circular linked list to play all the selected songs in a loop.
A circular linked list is used to store all the processes in execution by an operating system. It loops over the list repetitively until all the processes exit the system.
Allen Newell, Herbert A. Simon and J.C Shaw invent and implement linked lists and list processing for the development of artificial intelligence programs. List processing shows that programs need not have a fixed memory structure, that data structures can be chosen to suit the problem independent of hardware, and that symbol manipulation is the essence of computing.
Bobrow and Raphael at the RAND Corporation compare four prominent list-processing languages: COMIT, IPL-V, LISP 1.5 and SLIP. They note that these are good for handling complex data structures requiring dynamic and unpredictable memory allocations. They compare data representation, storage allocation, stack implementations and recursive operations. In general, by the early 1960s, some languages use linked lists as their primary data structure.
C++ Standard Template Library (STL) is released with support for the
list sequence container, which implements a doubly-linked list. This container can be used to implement stacks and queues. For example,
queue<list<int> > is a queue of integers using
list container. In the ISO C++ 11 standard (Sep 2011), STL includes a singly-linked list named
forward_list. This is more space-efficient compared to
- Bhola, Tanvy. 2021. "Applications of Linked list." OpenGenus, February 10. Accessed 2022-03-16.
- BigOCheatSheet. 2016. "Know Thy Complexities!" BigOCheatSheet, August 23. Accessed 2022-03-05.
- Bobrow, Daniel G., and Bertram Raphael. 1963. "A comparison of list-processing computer languages." Memorandum RM-3842-R, October. The RAND Corporation. Accessed 2022-04-05.
- Bogosavljević, Ivica. 2021. "The quest for the fastest linked list." Johny's Software Lab, August 04. Updated 2021-08-12. Accessed 2022-03-15.
- CMU. 2022. "Data Organization: Trees and Graphs." Carnegie Mellon University. Accessed 2022-03-15.
- Chan, Matthew. 2020. "Array vs Linked List Data Structures." Level Up Coding, on Medium, March 7. Accessed 2022-04-06.
- Cordeiro, Lucas. 2019. "COMP26120: Linked List in C." University of Manchester. Accessed 2022-03-15.
- Cppreference. 2021. "std::forward_list." Cppreference, September 14. Accessed 2022-04-05.
- Elgabry, Omar. 2016. "Data Structures — Language Support (Part 3)." On Medium, November 15. Accessed 2022-03-05.
- FacePrep. 2020. "Linked List." FacePrep, March 07. Accessed 2022-03-05.
- Gregg, Chris, and Julie Zelenski. 2020. "CS 106B: Programming Abstractions." Stanford. Updated 2020-05-18. Accessed 2022-03-05.
- Jamin, Sugih. 2011. "Lecture 4: Linked List, Basic ADTs." EECS 281 - Data Structures and Algorithms, University of Michigan, Fall 2011. Accessed 2022-03-05.
- Karumanchi, Narasimha. 2017. "Data Structures and Algorithms Made Easy." 5th edition, CareerMonk Publications. Accessed 2022-02-18.
- Kowal, Kris, and Benoit Marchant. 2016. "List." collections.js, June 08. Accessed 2022-03-16.
- Krohn, Hermann. 2019. "Linked Lists vs. Arrays." Towards Data Science. Accessed 2022-03-05.
- Minh, Nam Ha. 2022. "Java SE versions history." CodeJava. Accessed 2022-04-05.
- Mohapatra, Subasish. 2020. "Data Structures Using C." CET, Bhubaneswar. Accessed 2022-03-05.
- Newell, Allen and Herbert A. Simon. 2007. "Computer Science as Empirical Inquiry: Symbols and Search." ACM Turing Award Lectures, Association for Computing Machinery. Accessed 2022-03-05.
- OpenDSA. 2022a. "5.5. Comparison of List Implementations." CS3 Data Structures & Algorithms, OpenDSA, January 17. Accessed 2022-03-15.
- OpenDSA. 2022b. "5.4. Linked Lists." CS3 Data Structures & Algorithms, OpenDSA, January 17. Accessed 2022-04-05.
- Oracle. 2021. "Class LinkedList<E>." Java SE 17 & JDK 17, Oracle, September 13. Updated 2022-03-02. Accessed 2022-04-05.
- Pandav, Rohan. 2021. "Applications of data structure." Geek Culture, on Medium, April 14. Updated 2021-04-14. Accessed 2022-03-05.
- Stepanov, Alexander, and Meng Lee. 1995. "The Standard Template Library." Hewlett-Packard Company, October 31. Accessed 2022-03-17.
- Tang, Daisy. 2011. "Singly Linked List." Lecture notes, CS240: Data Structures and Algorithms I, Cal Poly Pomona. Accessed 2022-03-05.
- Tang, Daisy. 2011a. "Doubly Linked Lists and Circularly Linked Lists." Lecture notes, CS240: Data Structures and Algorithms I, Cal Poly Pomona. Accessed 2022-04-05.
- Thareja, Reema. 2014. "Data Structures Using C." Second edition, Oxford University Press. Accessed 2022-03-05.
- Uehara, Ryuhei, and Giovanni Viglietta. 2019. "Lesson 5. Data Structures (1): Linked List and Binary Search Tree." I111E – Algorithms and Data Structures, Japan Advanced Institute of Science and Technology, October 30. Accessed 2022-03-16.
- Wikipedia. 2021. "Reference (computer science)." Wikipedia, December 11. Accessed 2022-03-17.
- Wikipedia. 2022. "Linked list." Wikipedia, February 10. Accessed 2022-03-05.
- Padmaja, 2017. "Data Structures." Lecture notes, Institute of Aeronautical Engineering. Accessed 2022-03-05.
- Bullinaria, John. 2019. "Lecture notes for Data Structures and Algorithms." University of Birmingham, March 27. Accessed 2022-03-05.
- Bogosavljević, Ivica. 2021. "The quest for the fastest linked list." Johny's Software Lab, August 04. Updated 2021-08-12. Accessed 2022-03-15.
- Stack (Data Structure)
- Queue (Data Structure)
- Graph (Data Structure)
- Tree (Data Structure)
- Data Structures