Singly Linked Lists vs. Doubly Linked Lists: Choosing the Right Tool for the Job

Posted on in programming

cover image for article

Linked lists, fundamental data structures in computer science, offer dynamic memory allocation and efficient insertion and deletion operations. However, within the realm of linked lists, two prominent types emerge: singly linked lists and doubly linked lists. While both share core concepts, they possess distinct characteristics and suitability for specific scenarios. This article delves into a comparative analysis, equipping you to make informed decisions when choosing the right linked list for your programming needs.

1. Structure and Functionality

Singly Linked List:

  • Each node consists of data and a pointer to the next node in the sequence.
  • Insertion and deletion involve modifying pointers of surrounding nodes to bypass or insert the target node.
  • Traversal can only proceed in one direction, starting from the head and following the next pointers.

Doubly Linked List:

  • Each node contains data, a pointer to the next node, and a pointer to the previous node.
  • Enables efficient insertion and deletion at any position by adjusting both forward and backward pointers.
  • Supports bi-directional traversal, allowing movement from the head to the tail and vice versa.

2. Performance Considerations

Singly Linked List:

  • Generally faster insertions and deletions at the beginning or end compared to doubly linked lists due to fewer pointer modifications.
  • Traversal in one direction is slightly faster as only next pointers need to be followed.
  • Requires less memory per node as it only stores two pointers (data and next).

Doubly Linked List:

  • Slower insertions and deletions at the beginning or end due to the need to update both next and previous pointers.
  • Bi-directional traversal might be slower in some scenarios, especially for random access from the middle.
  • Consumes slightly more memory per node due to the additional previous pointer.

3. Use Cases and Suitability

Singly Linked List:

  • Ideal for scenarios where frequent insertions and deletions occur at the beginning or end of the list, such as stacks and queues.
  • Well-suited for situations where memory efficiency is a primary concern.
  • Examples: Implementing stacks for function calls, undo/redo functionality in text editors.

Doubly Linked List:

  • tercih when bi-directional traversal is essential, enabling efficient movement in both directions within the list.
  • Useful for representing graphs where nodes have connections in both directions.
  • Examples: Implementing caches or LRU (Least Recently Used) algorithms, representing musical playlists with forward and backward navigation.

4. Choosing the Right List

The optimal choice between singly and doubly linked lists hinges on the specific requirements of your application. Consider these factors:

  • Traversal needs: If bi-directional traversal is crucial, a doubly linked list is preferred.
  • Memory constraints: If memory efficiency is a top priority, a singly linked list might be advantageous.
  • Insertion/deletion patterns: Analyze the frequency and location of insertions and deletions to identify potential performance implications.

5. Example Implementations

C++

Singly Linked List:

#include <iostream>

class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
    }
};

class LinkedList {
public:
    Node* head;

    LinkedList() {
        head = nullptr;
    }

    // Insert a new node at the beginning of the list
    void insertAtBeginning(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }

    // Insert a new node at the end of the list
    void insertAtEnd(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            return;
        }

        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }

    // Delete the first node with the specified data value
    void deleteNode(int data) {
        if (head == nullptr) {
            return;
        }

        if (head->data == data) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        while (current->next != nullptr) {
            if (current->next->data == data) {
                Node* temp = current->next;
                current->next = current->next->next;
                delete temp;
                return;
            }
            current = current->next;
        }
    }

    // Print the data of all nodes in the list
    void printList() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

int main() {
    LinkedList list;

    list.insertAtBeginning(5);
    list.insertAtEnd(3);
    list.insertAtBeginning(1);

    std::cout << "List after insertions:" << std::endl;
    list.printList(); // Output: 1 -> 5 -> 3 -> nullptr

    list.deleteNode(3);

    std::cout << "List after deleting 3:" << std::endl;
    list.printList(); // Output: 1 -> 5 -> nullptr

    return 0;
}

Doubly Linked List:

#include <iostream>

class Node {
public:
    int data;
    Node* next;
    Node* prev;

    Node(int data) {
        this->data = data;
        this->next = nullptr;
        this->prev = nullptr;
    }
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() {
        head = nullptr;
    }

    // Insert a new node at the beginning of the list
    void insertAtBeginning(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            return;
        }

        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }

    // Insert a new node at the end of the list
    void insertAtEnd(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            return;
        }

        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
        newNode->prev = current;
    }

    // Delete the first node with the specified data value
    void deleteNode(int data) {
        if (head == nullptr) {
            return;
        }

        if (head->data == data) {
            if (head->next == nullptr) {
                delete head;
                head = nullptr;
                return;
            }

            head->next->prev = nullptr;
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node* current = head;
        while (current->next != nullptr) {
            if (current->next->data == data) {
                if (current->next->next == nullptr) {
                    current->next = nullptr;
                    delete current->next;
                    return;
                }

                current->next->next->prev = current;
                Node* temp = current->next;
                current->next = current->next->next;
                delete temp;
                return;
            }
            current = current->next;
        }
    }

    // Print the data of all nodes in the list
    void printList() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }
};

int main() {
    DoublyLinkedList list;

    list.insertAtBeginning(5);
    list.insertAtEnd(3);
    list.insertAtBeginning(1);

    std::cout << "List after insertions:" << std::endl;
    list.printList(); // Output: 1 -> 5 -> 3 -> nullptr

    list.deleteNode(3);

    std::cout << "List after deleting 3:" << std::endl;
    list.printList(); // Output: 1 -> 5 -> nullptr

    return 0;
}

Go

Singly Linked List:

package main

import "fmt"

// Node represents a single element in the linked list
type Node struct {
 Data int
 Next *Node
}

// LinkedList represents the entire linked list structure
type LinkedList struct {
 Head *Node
}

// InsertAtBeginning inserts a new node at the beginning of the list
func (l *LinkedList) InsertAtBeginning(data int) {
 newNode := &Node{Data: data}
 newNode.Next = l.Head
 l.Head = newNode
}

// InsertAtEnd inserts a new node at the end of the list
func (l *LinkedList) InsertAtEnd(data int) {
 newNode := &Node{Data: data}

 if l.Head == nil {
  l.Head = newNode
  return
 }

 current := l.Head
 for current.Next != nil {
  current = current.Next
 }
 current.Next = newNode
}

// Delete removes the first node with the specified data value
func (l *LinkedList) Delete(data int) {
 if l.Head == nil {
  return
 }

 if l.Head.Data == data {
  l.Head = l.Head.Next
  return
 }

 current := l.Head
 for current.Next != nil {
  if current.Next.Data == data {
   current.Next = current.Next.Next
   return
  }
  current = current.Next
 }
}

// PrintList iterates through the list and prints the data of each node
func (l *LinkedList) PrintList() {
 current := l.Head
 for current != nil {
  fmt.Printf("%d -> ", current.Data)
  current = current.Next
 }
 fmt.Println("nil")
}

func main() {
 linkedList := &LinkedList{}

 linkedList.InsertAtBeginning(5)
 linkedList.InsertAtEnd(3)
 linkedList.InsertAtBeginning(1)

 fmt.Println("List after insertions:")
 linkedList.PrintList() // Output: 1 -> 5 -> 3 -> nil

 linkedList.Delete(3)

 fmt.Println("List after deleting 3:")
 linkedList.PrintList() // Output: 1 -> 5 -> nil
}

Doubly Linked List:

package main

import "fmt"

// Node represents a single element in the linked list
type Node struct {
 Data int
 Next *Node
 Prev *Node
}

// LinkedList represents the entire linked list structure
type LinkedList struct {
 Head *Node
 Tail *Node
}

// InsertAtBeginning inserts a new node at the beginning of the list
func (l *LinkedList) InsertAtBeginning(data int) {
 newNode := &Node{Data: data}
 if l.Head == nil {
  l.Head = newNode
  l.Tail = newNode
  return
 }

 newNode.Next = l.Head
 l.Head.Prev = newNode
 l.Head = newNode
}

// InsertAtEnd inserts a new node at the end of the list
func (l *LinkedList) InsertAtEnd(data int) {
 newNode := &Node{Data: data}
 if l.Head == nil {
  l.Head = newNode
  l.Tail = newNode
  return
 }

 l.Tail.Next = newNode
 newNode.Prev = l.Tail
 l.Tail = newNode
}

// Delete removes the first node with the specified data value
func (l *LinkedList) Delete(data int) {
 if l.Head == nil {
  return
 }

 if l.Head.Data == data {
  if l.Head == l.Tail {
   l.Head = nil
   l.Tail = nil
   return
  }

  l.Head = l.Head.Next
  l.Head.Prev = nil
  return
 }

 current := l.Head
 for current != nil {
  if current.Data == data {
   if current.Next == nil {
    l.Tail = current.Prev
    l.Tail.Next = nil
   } else {
    current.Next.Prev = current.Prev
    current.Prev.Next = current.Next
   }
   return
  }
  current = current.Next
 }
}

// PrintList iterates through the list and prints the data of each node
func (l *LinkedList) PrintList() {
 current := l.Head
 for current != nil {
  fmt.Printf("%d -> ", current.Data)
  current = current.Next
 }
 fmt.Println("nil")
}

func main() {
 linkedList := &LinkedList{}

 linkedList.InsertAtBeginning(5)
 linkedList.InsertAtEnd(3)
 linkedList.InsertAtBeginning(1)

 fmt.Println("List after insertions:")
 linkedList.PrintList() // Output: 1 -> 5 -> 3 -> nil

 linkedList.Delete(3)

 fmt.Println("List after deleting 3:")
 linkedList.PrintList() // Output: 1 -> 5 -> nil
}

Java

Singly Linked List:

public class SinglyLinkedList {

    // Node class to represent each element in the linked list
    private class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Head of the linked list
    private Node head;

    // Insert a new node at the beginning of the list
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Insert a new node at the end of the list
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Delete the first node with the specified data value
    public void deleteNode(int data) {
        if (head == null) {
            return;
        }

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // Print the data of all nodes in the list
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.insertAtBeginning(5);
        list.insertAtEnd(3);
        list.insertAtBeginning(1);

        System.out.println("List after insertions:");
        list.printList(); // Output: 1 -> 5 -> 3 -> null

        list.deleteNode(3);

        System.out.println("List after deleting 3:");
        list.printList(); // Output: 1 -> 5 -> null
    }
}

Doubly Linked List:

public class DoublyLinkedList {

    // Node class to represent each element in the linked list
    private class Node {
        int data;
        Node prev;
        Node next;

        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    // Head and tail of the linked list
    private Node head;
    private Node tail;

    // Insert a new node at the beginning of the list
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            return;
        }

        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }

    // Insert a new node at the end of the list
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            return;
        }

        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    // Delete the first node with the specified data value
    public void deleteNode(int data) {
        if (head == null) {
            return;
        }

        if (head.data == data) {
            if (head == tail) {
                head = tail = null;
                return;
            }

            head = head.next;
            head.prev = null;
            return;
        }

        Node current = head;
        while (current != null) {
            if (current.data == data) {
                if (current.next == null) {
                    tail = current.prev;
                    tail.next = null;
                } else {
                    current.next.prev = current.prev;
                    current.prev.next = current.next;
                }
                return;
            }
            current = current.next;
        }
    }

    // Print the data of all nodes in the list
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();

        list.insertAtBeginning(5);
        list.insertAtEnd(3);
        list.insertAtBeginning(1);

        System.out.println("List after insertions:");
        list.printList(); // Output: 1 -> 5 -> 3 -> null

        list.deleteNode(3);

        System.out.println("List after deleting 3:");
        list.printList(); // Output: 1 -> 5 -> null
    }
}

Python

Singly Linked List:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next

        last_node.next = new_node

    def delete_node(self, data):
        if self.head is None:
            return

        if self.head.data == data:
            self.head = self.head.next
            return

        current_node = self.head
        while current_node.next:
            if current_node.next.data == data:
                current_node.next = current_node.next.next
                return
            current_node = current_node.next

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

if __name__ == "__main__":
    list = SinglyLinkedList()

    list.insert_at_beginning(5)
    list.insert_at_end(3)
    list.insert_at_beginning(1)

    print("List after insertions:")
    list.print_list()  # Output: 1 -> 5 -> 3 -> None

    list.delete_node(3)

    print("List after deleting 3:")
    list.print_list()  # Output: 1 -> 5 -> None

Doubly Linked List:

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def delete_node(self, data):
        if self.head is None:
            return

        current = self.head
        while current:
            if current.data == data:
                if current == self.head:
                    self.head = current.next
                    if self.head:
                        self.head.prev = None
                elif current == self.tail:
                    self.tail = current.prev
                    if self.tail:
                        self.tail.next = None
                else:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                return
            current = current.next

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

if __name__ == "__main__":
    list = DoublyLinkedList()

    list.insert_at_beginning(5)
    list.insert_at_end(3)
    list.insert_at_beginning(1)

    print("List after insertions:")
    list.print_list()  # Output: 1 -> 5 -> 3 -> None

    list.delete_node(3)

    print("List after deleting 3:")
    list.print_list()  # Output: 1 -> 5 -> None

Rust

Singly Linked List:

use std::ptr::null;

// Node struct representing a single element in the list
#[derive(Debug)]
struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

// SinglyLinkedList struct representing the entire linked list
pub struct SinglyLinkedList {
    head: Option<Box<Node>>,
}

impl SinglyLinkedList {
    // Create an empty linked list
    pub fn new() -> Self {
        SinglyLinkedList { head: None }
    }

    // Insert a new node at the beginning of the list
    pub fn insert_at_beginning(&mut self, data: i32) {
        let new_node = Box::new(Node { data, next: self.head.take() });
        self.head = Some(new_node);
    }

    // Insert a new node at the end of the list
    pub fn insert_at_end(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, next: None });
        if self.head.is_none() {
            self.head = Some(new_node);
            return;
        }

        let mut current = self.head.as_mut().unwrap();
        while let Some(ref mut next) = current.next {
            current = next;
        }
        current.next = Some(new_node);
    }

    // Delete the first node with the specified data value
    pub fn delete(&mut self, data: i32) {
        if self.head.is_none() {
            return;
        }

        if self.head.as_ref().unwrap().data == data {
            self.head = self.head.as_mut().unwrap().next.take();
            return;
        }

        let mut current = self.head.as_mut().unwrap();
        while let Some(ref mut next) = current.next {
            if next.data == data {
                current.next = next.next.take();
                return;
            }
            current = next;
        }
    }

    // Print the data of all nodes in the list
    pub fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = SinglyLinkedList::new();

    list.insert_at_beginning(5);
    list.insert_at_end(3);
    list.insert_at_beginning(1);

    println!("List after insertions:");
    list.print_list(); // Output: 1 -> 5 -> 3 -> null

    list.delete(3);

    println!("List after deleting 3:");
    list.print_list(); // Output: 1 -> 5 -> null
}

Doubly Linked List:

use std::ptr::null;

// Node struct representing a single element in the list
#[derive(Debug)]
struct Node {
    data: i32,
    prev: Option<Box<Node>>,
    next: Option<Box<Node>>,
}

// DoublyLinkedList struct representing the entire linked list
pub struct DoublyLinkedList {
    head: Option<Box<Node>>,
    tail: Option<Box<Node>>,
}

impl DoublyLinkedList {
    // Create an empty linked list
    pub fn new() -> Self {
        DoublyLinkedList { head: None, tail: None }
    }

    // Insert a new node at the beginning of the list
    pub fn insert_at_beginning(&mut self, data: i32) {
        let new_node = Box::new(Node {
            data,
            prev: None,
            next: self.head.take(),
        });
        if self.head.is_none() {
            self.tail = Some(new_node.clone());
        } else {
            self.head.as_mut().unwrap().prev = Some(new_node.clone());
        }
        self.head = Some(new_node);
    }

    // Insert a new node at the end of the list
    pub fn insert_at_end(&mut self, data: i32) {
        let new_node = Box::new(Node {
            data,
            prev: self.tail.clone(),
            next: None,
        });
        if self.tail.is_none() {
            self.head = Some(new_node.clone());
        } else {
            self.tail.as_mut().unwrap().next = Some(new_node.clone());
        }
        self.tail = Some(new_node);
    }

    // Delete the first node with the specified data value
    pub fn delete(&mut self, data: i32) {
        if self.head.is_none() {
            return;
        }

        if self.head.as_ref().unwrap().data == data {
            if self.head == self.tail {
                self.head = self.tail = None;
                return;
            }

            let mut next_node = self.head.as_mut().unwrap().next.take();
            next_node.as_mut().unwrap().prev = None;
            self.head = next_node;
            return;
        }

        let mut current = self.head.as_mut().unwrap();
        while let Some(ref mut next) = current.next {
            if next.data == data {
                if next.next.is_none() {
                    self.tail = current.clone();
                    current.next = None;
                } else {
                    next.next.as_mut().unwrap().prev = current.clone();
                    current.next = next.next.take();
                }
                return;
            }
            current = next;
        }
    }

    // Print the data of all nodes in the list
    pub fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();

    list.insert_at_beginning(5);
    list.insert_at_end(3);
    list.insert_at_beginning(1);

    println!("List after insertions:");
    list.print_list(); // Output: 1 -> 5 -> 3 -> null

    list.delete(3);

    println!("List after deleting 3:");
    list.print_list(); // Output: 1 -> 5 -> null
}

Remember, understanding the strengths and weaknesses of both singly and doubly linked lists empowers you to make informed decisions when selecting the appropriate data structure for your programming endeavors. By carefully evaluating your application's specific needs and trade-offs, you can leverage the unique capabilities of each linked list type to enhance efficiency and functionality.

Part 8 of the Data Structures series

data_structures cpp go java python rust

Slaptijack's Koding Kraken