Linked List Data Structure

A linked list is a linear collection of data elements, their order is not given by their physical placement in memory. Instead they are constructed in such a way that each element points to the next. It is a data structure that consists of a collection of nodes which together represents a sequence.

Linked lists can be singly or doubly linked.

Singly linked list

A singly linked list would use a node with data and only one reference (link) to the next node.

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

Full implementation

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

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

    def append(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            next_node = self.head
            while next_node.next:
                next_node = next_node.next
            next_node.next = Node(data)

    def push(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
    
    def insert(self, data, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1
                
            new_node = Node(data)
            if prev_node:
                prev_node.next = new_node
                new_node.next = next_node
            else:
                new_node.next = next_node
                self.head = new_node

    def pop(self):
        next_node = self.head
        prev_node = None
        while next_node.next:
            prev_node = next_node
            next_node = next_node.next
        prev_node.next = None
        return next_node.data
    
    def remove(self, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1

            if prev_node:
                prev_node.next = next_node.next
            else:
                self.head = next_node.next

    def reverse(self):
        prev_node = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev_node
            prev_node = current
            current = next_node

        self.head = prev_node
    
    def search(self, data):
        if not self.head:
            return "Not Found"
        else:
            next_node = self.head
            index = 0
            while next_node.data != data:
                next_node = next_node.next
                index += 1
                if not next_node:
                    return "Not Found"
            return index

    def sort(self):
        current_node = self.head
        next_node = None
        if not self.head:
            return
        else:
            while current_node:
                next_node = current_node.next

                while next_node:
                    if current_node.data > next_node.data:
                        current_node.data, next_node.data = next_node.data, current_node.data 
                    next_node = next_node.next
                
                current_node = current_node.next

    def print_list(self):
        next_node = self.head
        while next_node:
            print(next_node.data)
            next_node = next_node.next

import "fmt"

type DataType interface{}

type node struct {
	data DataType
	next *node
}

type LinkedList struct {
	head *node
	length int
}

func (l *LinkedList) IsEmpty() bool {
	return l.length == 0
}

func (l *LinkedList) Size() int {
	return l.length
}

func (l *LinkedList) Add(d DataType) {
	l.length++
	if l.head == nil {
		l.head = &node{d, nil}
	} else {
		temp := l.head
		for temp.next != nil {
			temp = temp.next
		}
		temp.next = &node{d, nil}
	}
}

func (l *LinkedList) Push(d DataType) {
	l.length++
	if l.head == nil {
		l.head = &node{d, nil}
	} else {
		temp := &node{d, nil}
		temp.next = l.head
		l.head = temp
	}
}

func (l *LinkedList) Pop() DataType {
	if l.IsEmpty() {
		return nil
	} else {
		l.length--
		temp := l.head.data
		l.head = l.head.next
		return temp
	}
}

func (l *LinkedList) Reverse() {
	head := l.head.next
	temp := l.head.next
	prev := l.head
	prev.next = nil
	keepGoing := true

	for keepGoing {
		temp = head
		head = head.next
		temp.next = prev
		prev = temp
		if head.next == nil {
			keepGoing = false
		}
	}
	head.next = temp
	l.head = head
}

func (l *LinkedList) PrintList() {
	temp := l.head
	keepGoing := true

	for keepGoing {
		fmt.Println(temp.data)
		if temp.next != nil {
			temp = temp.next
		} else {
			keepGoing = false
		}
	}
}

class Node {
    constructor(data, next=null) {
        this.data = data;
        this.next = next;
    }
}
  
class LinkedList {
    constructor(head=null) {
        this.head = head;
    }
    // add item to end of the list
    append(item) {
        if (this.head === null) {
            this.head = new Node(item);
        } else {
            let next = this.head;
            while (next.next !== null) {
                next = next.next;
            }
            next.next = new Node(item);
        }
    }
    // add item to the front of the list
    push(item) {
        if (this.head === null) {
            this.head = new Node(item);
        } else {
            let temp = new Node(item);
            temp.next = this.head;
            this.head = temp;
        }
    }
    // pop (remove) from end of the list
    pop() {
        let next = this.head;
        let prev = null;
        while (next.next !== null) {
            prev = next;
            next = next.next;
        }
        prev.next = null;
        return next.data;
    }
    // search if node value in list and return bool
    searchNode(item) {
        let next = this.head;
        while (next !== null) {
            if (next.data === item) {
                return true;
            }
            next = next.next;
        }
        return false;
    }
    // traverse list and print each item
    print_list() {
        let next = this.head;
        while (next !== null) {
            print(next.data);
            next = next.next;
        }
    }
    // turn list around
    reverse() {
        let next = this.head;
        let prev = null;
        let curr;
          
        while (next !== null) {
            curr = next;
            next = curr.next;
            curr.next = prev;
            prev = curr;
        }
        this.head = prev;
    }
}

using namespace std;

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

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

// Define LinkedList class
class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = nullptr;
    }

    // Append method
    void append(int data) {
        if (head == nullptr) {
            head = new Node(data);
        } else {
            Node* next_node = head;
            while (next_node->next) {
                next_node = next_node->next;
            }
            next_node->next = new Node(data);
        }
    }

    // Push method
    void push(int data) {
        Node* new_node = new Node(data);
        new_node->next = head;
        head = new_node;
    }

    // Insert method
    void insert(int data, int index) {
        if (index < 0) {
            cout << "Index out of range." << endl;
            return;
        }

        Node* next_node = head;
        Node* prev_node = nullptr;
        int curr_index = 0;

        while (next_node != nullptr && curr_index < index) {
            prev_node = next_node;
            next_node = next_node->next;
            curr_index++;
        }

        if (next_node == nullptr && curr_index < index) {
            cout << "Index out of range." << endl;
            return;
        }

        Node* new_node = new Node(data);
        if (prev_node) {
            prev_node->next = new_node;
            new_node->next = next_node;
        } else {
            new_node->next = next_node;
            head = new_node;
        }
    }

    // Pop method
    int pop() {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return -1; // Return an error value
        }

        Node* next_node = head;
        Node* prev_node = nullptr;

        while (next_node->next) {
            prev_node = next_node;
            next_node = next_node->next;
        }

        int data = next_node->data;
        if (prev_node) {
            prev_node->next = nullptr;
        } else {
            head = nullptr;
        }

        delete next_node;  // Free the memory of the popped node
        return data;
    }

    // Remove method
    void remove(int index) {
        if (index < 0 || head == nullptr) {
            cout << "Index out of range." << endl;
            return;
        }

        Node* next_node = head;
        Node* prev_node = nullptr;
        int curr_index = 0;

        while (next_node != nullptr && curr_index < index) {
            prev_node = next_node;
            next_node = next_node->next;
            curr_index++;
        }

        if (next_node == nullptr) {
            cout << "Index out of range." << endl;
            return;
        }

        if (prev_node) {
            prev_node->next = next_node->next;
        } else {
            head = next_node->next;
        }

        delete next_node;  // Free memory of removed node
    }

    // Reverse method
    void reverse() {
        Node* prev_node = nullptr;
        Node* current = head;
        Node* next_node = nullptr;

        while (current != nullptr) {
            next_node = current->next;
            current->next = prev_node;
            prev_node = current;
            current = next_node;
        }

        head = prev_node;
    }

    // Search method
    int search(int data) {
        Node* next_node = head;
        int index = 0;

        while (next_node != nullptr) {
            if (next_node->data == data) {
                return index;
            }
            next_node = next_node->next;
            index++;
        }

        return -1; // Return -1 if not found
    }

    // Sort method
    void sort() {
        if (head == nullptr) {
            return;
        }

        Node* current_node = head;
        Node* next_node = nullptr;

        while (current_node != nullptr) {
            next_node = current_node->next;

            while (next_node != nullptr) {
                if (current_node->data > next_node->data) {
                    swap(current_node->data, next_node->data);
                }
                next_node = next_node->next;
            }

            current_node = current_node->next;
        }
    }

    // Print list method
    void print_list() {
        Node* next_node = head;
        while (next_node != nullptr) {
            cout << next_node->data << endl;
            next_node = next_node->next;
        }
    }

    ~LinkedList() {
        Node* current = head;
        Node* next_node = nullptr;

        while (current != nullptr) {
            next_node = current->next;
            delete current;
            current = next_node;
        }
    }
};

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Constructor
    public LinkedList() {
        head = null;
    }

    // Append method
    public void append(int data) {
        if (head == null) {
            head = new Node(data);
        } else {
            Node nextNode = head;
            while (nextNode.next != null) {
                nextNode = nextNode.next;
            }
            nextNode.next = new Node(data);
        }
    }

    // Push method
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Insert method
    public void insert(int data, int index) {
        if (index < 0) {
            System.out.println("Index out of range.");
            return;
        }

        Node nextNode = head;
        Node prevNode = null;
        int currIndex = 0;

        while (nextNode != null && currIndex < index) {
            prevNode = nextNode;
            nextNode = nextNode.next;
            currIndex++;
        }

        if (nextNode == null && currIndex < index) {
            System.out.println("Index out of range.");
            return;
        }

        Node newNode = new Node(data);
        if (prevNode != null) {
            prevNode.next = newNode;
            newNode.next = nextNode;
        } else {
            newNode.next = nextNode;
            head = newNode;
        }
    }

    // Pop method
    public int pop() {
        if (head == null) {
            System.out.println("List is empty.");
            return -1; // Error value
        }

        Node nextNode = head;
        Node prevNode = null;

        while (nextNode.next != null) {
            prevNode = nextNode;
            nextNode = nextNode.next;
        }

        int data = nextNode.data;
        if (prevNode != null) {
            prevNode.next = null;
        } else {
            head = null;
        }

        return data;
    }

    // Remove method
    public void remove(int index) {
        if (index < 0 || head == null) {
            System.out.println("Index out of range.");
            return;
        }

        Node nextNode = head;
        Node prevNode = null;
        int currIndex = 0;

        while (nextNode != null && currIndex < index) {
            prevNode = nextNode;
            nextNode = nextNode.next;
            currIndex++;
        }

        if (nextNode == null) {
            System.out.println("Index out of range.");
            return;
        }

        if (prevNode != null) {
            prevNode.next = nextNode.next;
        } else {
            head = nextNode.next;
        }
    }

    // Reverse method
    public void reverse() {
        Node prevNode = null;
        Node current = head;
        Node nextNode = null;

        while (current != null) {
            nextNode = current.next;
            current.next = prevNode;
            prevNode = current;
            current = nextNode;
        }

        head = prevNode;
    }

    // Search method
    public int search(int data) {
        Node nextNode = head;
        int index = 0;

        while (nextNode != null) {
            if (nextNode.data == data) {
                return index;
            }
            nextNode = nextNode.next;
            index++;
        }

        return -1; // Not found
    }

    // Sort method
    public void sort() {
        if (head == null) {
            return;
        }

        Node currentNode = head;
        Node nextNode = null;

        while (currentNode != null) {
            nextNode = currentNode.next;

            while (nextNode != null) {
                if (currentNode.data > nextNode.data) {
                    int temp = currentNode.data;
                    currentNode.data = nextNode.data;
                    nextNode.data = temp;
                }
                nextNode = nextNode.next;
            }

            currentNode = currentNode.next;
        }
    }

    // Print list method
    public void printList() {
        Node nextNode = head;
        while (nextNode != null) {
            System.out.println(nextNode.data);
            nextNode = nextNode.next;
        }
    }
}

Doubly linked list

A doubly linked list would use a node with data and two references (links) which would point to the next and previous nodes.

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

Full implementation

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

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

    def append(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            next_node = self.head
            while next_node.next:
                next_node = next_node.next
            next_node.next = Node(data)

    def push(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
    
    def insert(self, data, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1
                
            new_node = Node(data)
            if prev_node:
                prev_node.next = new_node
                new_node.next = next_node
            else:
                new_node.next = next_node
                self.head = new_node

    def pop(self):
        next_node = self.head
        prev_node = None
        while next_node.next:
            prev_node = next_node
            next_node = next_node.next
        prev_node.next = None
        return next_node.data
    
    def remove(self, index):
        if not self.head and index > 0 or index < 0:
            return "Index out of range."
        else:
            next_node = self.head
            prev_node = None
            curr_index = 0
            while curr_index != index:
                prev_node = next_node
                next_node = next_node.next
                curr_index += 1

            if prev_node:
                prev_node.next = next_node.next
            else:
                self.head = next_node.next

    def reverse(self):
        prev_node = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev_node
            prev_node = current
            current = next_node

        self.head = prev_node
    
    def search(self, data):
        if not self.head:
            return "Not Found"
        else:
            next_node = self.head
            index = 0
            while next_node.data != data:
                next_node = next_node.next
                index += 1
                if not next_node:
                    return "Not Found"
            return index

    def sort(self):
        current_node = self.head
        next_node = None
        if not self.head:
            return
        else:
            while current_node:
                next_node = current_node.next

                while next_node:
                    if current_node.data > next_node.data:
                        current_node.data, next_node.data = next_node.data, current_node.data 
                    next_node = next_node.next
                
                current_node = current_node.next

    def print_list(self):
        next_node = self.head
        while next_node:
            print(next_node.data)
            next_node = next_node.next

Time Complexity

Here’s a table summarizing the time complexities for various operations on single and double linked lists:

Operation	Single Linked List	Double Linked List
Access (by index)	O(n)	O(n)
Search (by value)	O(n)	O(n)
Insertion (beginning)	O(1)	O(1)
Insertion (end)	O(n)	O(1)
Insertion (middle)	O(n)	O(n)
Deletion (beginning)	O(1)	O(1)
Deletion (end)	O(n)	O(1)
Deletion (middle)	O(n)	O(n)
Traversal	O(n)	O(n)

Explanation:

Single Linked List: Each node only contains a reference to the next node, so operations that involve traversing the list or accessing an arbitrary index generally take O(n) time.
Double Linked List: Each node contains references to both the next and previous nodes. This makes certain operations, like deletion from the end or inserting at the end, more efficient (O(1)) compared to a singly linked list. However, accessing an arbitrary index still requires traversal, so it remains O(n) for both types of lists.

Posted on Mar 26, 2019 by bmcculley Posted in:

Data Structures