Home
Data Structures

Linked Lists: Functions and Differences

 


Functions of Each Linked List Type

Singly Linked List

  • Insertion

    • At the beginning, end, or at a specific position in the list

  • Deletion

    • Remove a node from the beginning, end, or a given position

  • Traversal

    • Access all elements sequentially from head to tail

  • Search

    • Locate the position of a node containing a specific value

  • Update

    • Change the value of data in a given node

  • Length/Count

    • Calculate the number of nodes in the list

  • IsEmpty

    • Check if the list is empty

Diagram (text):


[Data|Next] → [Data|Next] → [Data|Next] → NULL

Circular Linked List

  • Insertion

    • At the beginning, end, or any given position within the loop

  • Deletion

    • Remove a node from the start, end, or a specific position (ensuring the circular structure remains)

  • Traversal

    • Visit all nodes starting from any node and returning to the same node

  • Search

    • Find if an element exists by looping through the nodes

  • Update

    • Change the value in a node

  • IsEmpty

    • Check if the list has no nodes.

Diagram (text):


[Data|Next] → [Data|Next] → [Data|Next]
      ↑                           |
      |___________________________|

Doubly Linked List

  • Insertion

    • At the beginning, end, after or before a specific node

  • Deletion

    • Remove nodes from the start, end, or specified value

  • Traversal

    • Forward traversal: head to tail

    • Backward traversal: tail to head (unique to doubly linked list)

  • Search

    • Find a node with a specific value from either direction

  • Update

    • Modify the data in a node

  • IsEmpty

    • Check if the list is empty.

Diagram (text):
text
NULL ← [Prev|Data|Next] ↔ [Prev|Data|Next] ↔ [Prev|Data|Next] → NULL

Differences Between Singly, Circular, and Doubly Linked Lists

FeatureSingly Linked ListCircular Linked ListDoubly Linked List
StructureEach node points to the next nodeLast node points back to head node (no NULL at end)Node has pointers to both next and previous nodes
NavigationForward onlyForward (continuous loop)Forward and backward
First Node PointsOnly to next nodeOnly to next node (could be head in the loop)To next node and previous (NULL for previous in head node)
Last Node PointsTo NULLTo head nodeNext is NULL, previous is last valid node
Memory UsageLeast (1 pointer/node)Slightly more (to track circle)Most (2 pointers/node)
Insertion/DeletionO(1) at head; O(n) elsewhereO(1) at head/tail if last pointer tracked; O(n) elsewhereO(1) anywhere if node pointer given
TraversalOnly from head to tail; stops at NULLFrom head continuously, ends after full cycleFrom head to tail and vice-versa; stops at NULL in either end
Use CasesSimple lists, stacksRound-robin, circular queuesComplex navigation (undo/redo, bidirectional traversal)
Implementation ComplexitySimpleModerate (must handle looping conditions)Complex (must maintain previous/next links for every insert/delete)
Bidirectional SupportNoNo (unless doubly circular)Yes

Everyday Applications

1. Web Browsers (Back and Forward Navigation)

  • Browsers use doubly linked lists to manage the history of visited webpages.

  • Each node represents a webpage, allowing users to traverse back and forth efficiently through their navigation history12.

2. Music and Video Playlists

  • Playlists in music or video apps often use singly or doubly linked lists so tracks can be played in sequence, and you can easily jump to the next or previous item without the need to shift all contents324.

3. Image Viewers

  • Viewing photos on laptops or devices lets users move to the next or previous image seamlessly.

  • This is enabled by linking images as nodes in a list, facilitating quick sequential access32.

4. Task Scheduling in Operating Systems

  • Operating systems manage processes using linked lists. Each running or waiting process is represented as a node.

  • These lists allow for quick addition, removal, and traversal of processes during scheduling and execution3.

5. Undo/Redo Functionality

  • Many applications (like text editors) use doubly linked lists to implement the undo and redo stacking of actions. Each user action becomes a node, enabling reversal or reapplication of changes31.

6. Social Media Feeds

  • Social networks often manage posts and updates in a list structure; navigating through previous or next posts is enabled by this design14.

7. Train Coaches and Other Physical Examples

  • Trains can be viewed as a doubly linked list: each carriage connects to the next and previous ones, allowing efficient detachment or reordering, directly reflecting linked list operations5.

  • Similarly, a line (queue) of people or cars, where individuals are connected in sequence, can be modeled as a singly linked list5.

Special Use Cases

Use CaseLinked List VariantDescription
Web browser historyDoubly linked listSupports both backward and forward navigation12
Media playlistsSingly/doubly linkedSequentially play, add, or remove songs/videos without moving all items324
Image viewersDoubly linked listNavigate next/previous images efficiently32
OS process schedulingSingly/circular linkedManage running/waiting processes with dynamic addition/removal3
Undo/redo in editorsDoubly linked listTraverse actions forwards and backwards for undo/redo functionality31
Task queuesSingly/circular linkedUsed in printers, customer management, networking,35
Train coachesDoubly linked listPhysical analogy—carriages connect to both previous and next5

Key Benefits in Practice

  • Dynamic memory usage: Linked lists adapt to varying sizes with frequent insertions/deletions.

  • Flexible data management: Nodes can be added or removed anywhere in constant time (if node references are known), ideal for implementing features like playlists, navigation, and scheduling.

  • Bidirectional traversal: With doubly linked lists, users navigate back and forth seamlessly, as seen in browser navigation and media controls.

Linked lists serve as the backbone for many user-facing features and hidden system processes, ensuring dynamic operations and efficient data organization in modern applications.