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;
    }
} 

int binarySearch(vector nums, int x) {
	int left = 0;
	int right = nums.size();

	while (left <= right) {
		int mid = left + (right - left) / 2;

		if (nums[mid] == x)
			return mid;
		if (nums[mid] < x)
			left = mid + 1;
		else
			right = mid - 1;
  	}
  	return -1;
}

public class BinarySearch {

    public static int search(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

}

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

Singly Linked List

Explanation:

• Insertion (Front): Inserting a new node at the front of a linked list involves creating a new node and updating the head pointer to point to the new node. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.

• Insertion (Back): Inserting a new node at the back of a linked list involves traversing the entire list to reach the last node and then appending the new node to the end. In the best and average cases, when a reference to the last node is maintained, this operation has a constant time complexity of (O(1)). However, in the worst case, when the reference to the last node is not available, traversal to the last node takes linear time (O(n)).

• Insertion (Middle): Inserting a new node in the middle of a linked list involves traversing to the desired position and updating the pointers of the adjacent nodes to include the new node. In the best case, when the insertion position is known, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when traversal is required, this operation takes linear time (O(n)).

• Deletion (Front): Deleting the first node of a linked list involves updating the head pointer to point to the second node. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.

• Deletion (Back): Deleting the last node of a linked list involves traversing the entire list to reach the second-to-last node and updating its next pointer to None. In the best and average cases, when a reference to the last node is maintained, this operation takes linear time (O(n)). However, in the worst case, when the reference to the last node is not available, traversal to the second-to-last node also takes linear time (O(n)).

• Deletion (Middle): Deleting a node from the middle of a linked list involves traversing to the node to be deleted and updating the pointers of the adjacent nodes to bypass the deleted node. In the best case, when the deletion position is known, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when traversal is required, this operation takes linear time (O(n)).

• Search: Searching for a node with a given value in a linked list involves traversing the entire list until the target node is found. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when the target node is not found until the end of the list, this operation takes linear time (O(n)).

• Access: Accessing the value of a node at a given index in a linked list involves traversing the list until the target node is reached. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average and worst cases, when the target node is at the end of the list or not found, this operation takes linear time (O(n)).

• Length: Determining the length of a linked list involves traversing the entire list and counting the number of nodes. This operation has a constant time complexity of (O(1)) in all cases because a reference to the last node can be maintained to avoid traversal.

Doubly Linked List

Explanation:

• Insertion (Front): Inserting a new node at the front of a doubly linked list involves creating a new node, updating pointers, and updating the head pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.

• Insertion (Back): Inserting a new node at the back of a doubly linked list involves creating a new node, updating pointers, and updating the tail pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.

• Insertion (Middle): Inserting a new node in the middle of a doubly linked list involves traversing to the desired position and updating pointers. In the best case, when the insertion position is known, this operation has a constant time complexity of (O(1)). However, in the average case, when the insertion position is in the middle of the list, traversal takes (O(n/2)) time, and the worst-case time complexity is (O(n)) when the insertion position is at the end of the list.

• Deletion (Front): Deleting the first node of a doubly linked list involves updating pointers and updating the head pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.

• Deletion (Back): Deleting the last node of a doubly linked list involves updating pointers and updating the tail pointer. This operation has a constant time complexity of (O(1)) in all cases because it does not depend on the size of the list.

• Deletion (Middle): Deleting a node from the middle of a doubly linked list involves traversing to the desired position and updating pointers. In the best case, when the deletion position is known, this operation has a constant time complexity of (O(1)). However, in the average case, when the deletion position is in the middle of the list, traversal takes (O(n/2)) time, and the worst-case time complexity is (O(n)) when the deletion position is at the end of the list.

• Search: Searching for a node with a given value in a doubly linked list involves traversing the list until the target node is found. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average case, when the target node is in the middle of the list, traversal takes (O(n/2)) time, and the worst-case time complexity is (O(n)) when the target node is at the end of the list.

• Access: Accessing the value of a node at a given index in a doubly linked list involves traversing the list until the target node is reached. In the best case, when the target node is at the front of the list, this operation has a constant time complexity of (O(1)). However, in the average case, when the target node is in the middle of the list