Linked List Code Implementation

labuladongOriginalAbout 6371 words

Prerequisites

Before reading this article, you should first learn:

Basics of Linked Lists (Linked Storage)

Key Points

I will present a simple implementation of MyLinkedList using both doubly and singly linked lists, including basic operations like adding, removing, and updating elements. Here are some key points to focus on when reviewing the code.

Key Point 1: Holding References to Both Head and Tail Nodes

In LeetCode problems, we are typically provided with the head pointer of a singly linked list. However, in real-world development, doubly linked lists are used more frequently, and they generally hold references to both the head and tail nodes.

In software development, adding elements to the end of a container is a very common operation. By holding a reference to the tail node, a doubly linked list can perform this operation in $O(1)$ time complexity.

For singly linked lists, holding a reference to the tail node also offers optimization. For instance, if you need to add an element to the end of a singly linked list and you do not have a reference to the tail node, you must traverse the entire list to find the tail, which has a time complexity of $O(n)$ . With a reference to the tail node, you can perform the addition in $O(1)$ time complexity.

Attentive readers might point out that if you delete the tail node of a singly linked list, the reference to the previous tail becomes invalid, requiring a traversal to find the new tail node.

That's correct. However, consider this: when deleting the tail node of a singly linked list, you need to traverse to the second-to-last node (the predecessor of the tail) to delete the tail node through pointer manipulation. At this point, you can update the tail node reference conveniently.

Key Point Two: Dummy Head and Tail Nodes

In the previous article Linked List Basics, I mentioned the "dummy head and tail node" technique. The concept is simple: when creating a doubly linked list, a dummy head node and a dummy tail node are established, and these nodes exist whether the list is empty or not. This approach prevents null pointer issues and simplifies handling many edge cases.

For example, assume the dummy head and tail nodes are dummyHead and dummyTail, then an empty doubly linked list looks like this:

dummyHead <-> dummyTail

If you add elements 1, 2, 3, the list will look like this:

dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail

Previously, you needed to separately handle cases for inserting elements at the head, tail, and in the middle of the list. With dummy head and tail nodes, regardless of whether the list is empty, you only need to consider inserting elements in the middle. This simplifies the code significantly.

Of course, the dummy head node does consume a little extra memory space, but compared to the issues it resolves, this space consumption is worthwhile.

For singly linked lists, a dummy head node simplifies some operations, but a dummy tail node is not very useful.

Dummy Nodes Are Internal and Invisible

Dummy nodes are a technique for implementing data structures internally and are invisible externally. For instance, the get(index) method to retrieve an element by index calculates the index from real nodes, not from dummy nodes.

Key Point Three: Memory Leak?

In the previous article Dynamic Array Implementation, I mentioned the issue of memory leaks when deleting elements. So, does deleting elements in a linked list also lead to memory leaks?

Especially with the following code, do you think there is an issue?

// Assume the head node of the singly linked list is head = 1 -> 2 -> 3 -> 4 -> 5

// Delete the head node of the singly linked list
head = head.next;

// At this point, head = 2 -> 3 -> 4 -> 5

Attentive readers might think that this approach could lead to a memory leak because the next pointer of the original head node 1 is not disconnected and still points to node 2.

However, this way of writing is acceptable because Java's garbage collection mechanism determines whether an object is referenced by others and does not care if the object itself still references others.

The next pointer of node 1 indeed still points to node 2, but since no other pointers reference node 1, it will eventually be collected and released by the garbage collector. Therefore, this scenario differs from deleting elements in an array, and you might want to think about it more.

Nonetheless, when deleting a node, it is good practice to set the pointers of the deleted node to null. This habit has no downside and might prevent some potential issues. Hence, in the following implementation, I will set the pointers of the deleted node to null, whether necessary or not.

How to Validate Your Implementation?

You can use LeetCode problem 707 "Design Linked List" to verify if your implementation is correct.

Doubly Linked List Code Implementation

java 🟢

import java.util.NoSuchElementException;

public class MyLinkedList<E> {
    // virtual head and tail nodes
    final private Node<E> head, tail;
    private int size;

    // doubly linked list node
    private static class Node<E> {
        E val;
        Node<E> next;
        Node<E> prev;

        Node(E val) {
            this.val = val;
        }
    }

    // constructor initializes virtual head and tail nodes
    public MyLinkedList() {
        this.head = new Node<>(null);
        this.tail = new Node<>(null);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }


    // ***** Add *****

    public void addLast(E e) {
        Node<E> x = new Node<>(e);
        Node<E> temp = tail.prev;
        // temp <-> tail
        temp.next = x;
        x.prev = temp;

        x.next = tail;
        tail.prev = x;
        // temp <-> x <-> tail
        size++;
    }

    public void addFirst(E e) {
        Node<E> x = new Node<>(e);
        Node<E> temp = head.next;
        // head <-> temp
        temp.prev = x;
        x.next = temp;

        head.next = x;
        x.prev = head;
        // head <-> x <-> temp
        size++;
    }

    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size) {
            addLast(element);
            return;
        }

        // find the Node corresponding to index
        Node<E> p = getNode(index);
        Node<E> temp = p.prev;
        // temp <-> p

        // new Node to be inserted
        Node<E> x = new Node<>(element);

        p.prev = x;
        temp.next = x;

        x.prev = temp;
        x.next = p;

        // temp <-> x <-> p

        size++;
    }

    // ***** Remove *****

    public E removeFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        // the existence of virtual nodes prevents us from having to consider null pointers
        Node<E> x = head.next;
        Node<E> temp = x.next;
        // head <-> x <-> temp
        head.next = temp;
        temp.prev = head;

        x.prev = null;
        x.next = null;
        // head <-> temp

        size--;
        return x.val;
    }

    public E removeLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }
        Node<E> x = tail.prev;
        Node<E> temp = tail.prev.prev;
        // temp <-> x <-> tail

        tail.prev = temp;
        temp.next = tail;

        x.prev = null;
        x.next = null;
        // temp <-> tail

        size--;
        return x.val;
    }

    public E remove(int index) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node<E> x = getNode(index);
        Node<E> prev = x.prev;
        Node<E> next = x.next;
        // prev <-> x <-> next
        prev.next = next;
        next.prev = prev;

        x.prev = x.next = null;
        // prev <-> next

        size--;

        return x.val;
    }

    // ***** Get *****

    public E get(int index) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node<E> p = getNode(index);

        return p.val;
    }

    public E getFirst() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        return head.next.val;
    }

    public E getLast() {
        if (size < 1) {
            throw new NoSuchElementException();
        }

        return tail.prev.val;
    }

    // ***** Set *****

    public E set(int index, E val) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node<E> p = getNode(index);

        E oldVal = p.val;
        p.val = val;

        return oldVal;
    }

    // ***** Other utility functions *****

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private Node<E> getNode(int index) {
        checkElementIndex(index);
        Node<E> p = head.next;
        // TODO: Can be optimized by deciding
        // whether to traverse from head or tail
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    // Check if the index position can contain an element
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // Check if the index position can add an element
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    private void display() {
        System.out.println("size = " + size);
        for (Node<E> p = head.next; p != tail; p = p.next) {
            System.out.print(p.val + " <-> ");
        }
        System.out.println("null");
        System.out.println();
    }

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addFirst(0);
        list.add(2, 100);

        list.display();
        // size = 5
        // 0 <-> 1 <-> 100 <-> 2 -> 3 -> null
    }
}

cpp 🤖

#include <iostream>
#include <stdexcept>

template<typename E>
class MyLinkedList {
    // virtual head and tail nodes
    struct Node {
        E val;
        Node* next;
        Node* prev;

        Node(E value) : val(value), next(nullptr), prev(nullptr) {}
    };

    Node* head;
    Node* tail;
    int size;

public:
    // constructor initializes virtual head and tail nodes
    MyLinkedList() {
        head = new Node(E());
        tail = new Node(E());
        head->next = tail;
        tail->prev = head;
        size = 0;
    }

    // ***** Add *****

    void addLast(E e) {
        Node* x = new Node(e);
        Node* temp = tail->prev;
        // temp <-> tail
        temp->next = x;
        x->prev = temp;

        x->next = tail;
        tail->prev = x;
        // temp <-> x <-> tail
        size++;
    }

    void addFirst(E e) {
        Node* x = new Node(e);
        Node* temp = head->next;
        // head <-> temp
        temp->prev = x;
        x->next = temp;

        head->next = x;
        x->prev = head;
        // head <-> x <-> temp
        size++;
    }

    void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size) {
            addLast(element);
            return;
        }

        // find the Node corresponding to index
        Node* p = getNode(index);
        Node* temp = p->prev;
        // temp <-> p

        // new Node to be inserted
        Node* x = new Node(element);

        p->prev = x;
        temp->next = x;

        x->prev = temp;
        x->next = p;

        // temp <-> x <-> p

        size++;
    }

    // ***** Remove *****

    E removeFirst() {
        if (size < 1) {
            throw std::out_of_range("No elements to remove");
        }
        // the existence of virtual nodes prevents us from having to consider null pointers
        Node* x = head->next;
        Node* temp = x->next;
        // head <-> x <-> temp
        head->next = temp;
        temp->prev = head;

        delete x;
        // head <-> temp

        size--;
        return temp->val;
    }

    E removeLast() {
        if (size < 1) {
            throw std::out_of_range("No elements to remove");
        }
        Node* x = tail->prev;
        Node* temp = tail->prev->prev;
        // temp <-> x <-> tail

        tail->prev = temp;
        temp->next = tail;

        delete x;
        // temp <-> tail

        size--;
        return temp->val;
    }

    E remove(int index) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node* x = getNode(index);
        Node* prev = x->prev;
        Node* next = x->next;
        // prev <-> x <-> next
        prev->next = next;
        next->prev = prev;

        delete x;
        // prev <-> next

        size--;

        return next->val;
    }

    // ***** Get *****

    E get(int index) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node* p = getNode(index);

        return p->val;
    }

    E getFirst() {
        if (size < 1) {
            throw std::out_of_range("No elements in the list");
        }

        return head->next->val;
    }

    E getLast() {
        if (size < 1) {
            throw std::out_of_range("No elements in the list");
        }

        return tail->prev->val;
    }

    // ***** Set *****

    E set(int index, E val) {
        checkElementIndex(index);
        // find the Node corresponding to index
        Node* p = getNode(index);

        E oldVal = p->val;
        p->val = val;

        return oldVal;
    }

    // ***** Other utility functions *****

    int getSize() const {
        return size;
    }

    bool isEmpty() const {
        return size == 0;
    }

private:
    Node* getNode(int index) {
        checkElementIndex(index);
        Node* p = head->next;
        // TODO: Can be optimized by deciding
        // whether to traverse from head or tail
        for (int i = 0; i < index; i++) {
            p = p->next;
        }
        return p;
    }

    bool isElementIndex(int index) const {
        return index >= 0 && index < size;
    }

    bool isPositionIndex(int index) const {
        return index >= 0 && index <= size;
    }

    // Check if the index position can contain an element
    void checkElementIndex(int index) const {
        if (!isElementIndex(index))
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
    }

    // Check if the index position can add an element
    void checkPositionIndex(int index) const {
        if (!isPositionIndex(index))
            throw std::out_of_range("Index: " + std::to_string(index) + ", Size: " + std::to_string(size));
    }

public:
    void display() {
        std::cout << "size = " << size << std::endl;
        for (Node* p = head->next; p != tail; p = p->next) {
            std::cout << p->val << " <-> ";
        }
        std::cout << "null" << std::endl;
        std::cout << std::endl;
    }

    ~MyLinkedList() {
        while (size > 0) {
            removeFirst();
        }
        delete head;
        delete tail;
    }
};

int main() {
    MyLinkedList<int> list;
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.add(2, 100);

    list.display();
    // size = 5
    // 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null

    return 0;
}

python 🤖

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

class MyLinkedList:
    # virtual head and tail nodes
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    # ***** Add *****

    def add_last(self, e):
        x = Node(e)
        temp = self.tail.prev
        # temp <-> tail
        temp.next = x
        x.prev = temp

        x.next = self.tail
        self.tail.prev = x
        # temp <-> x <-> tail
        self.size += 1

    def add_first(self, e):
        x = Node(e)
        temp = self.head.next
        # head <-> temp
        temp.prev = x
        x.next = temp

        self.head.next = x
        x.prev = self.head
        # head <-> x <-> temp
        self.size += 1

    def add(self, index, element):
        self.check_position_index(index)
        if index == self.size:
            self.add_last(element)
            return

        # find the Node corresponding to index
        p = self.get_node(index)
        temp = p.prev
        # temp <-> p

        # new Node to be inserted
        x = Node(element)

        p.prev = x
        temp.next = x

        x.prev = temp
        x.next = p

        # temp <-> x <-> p

        self.size += 1

    # ***** Remove *****

    def remove_first(self):
        if self.size < 1:
            raise IndexError("No elements to remove")
        # the existence of virtual nodes prevents us from having to consider null pointers
        x = self.head.next
        temp = x.next
        # head <-> x <-> temp
        self.head.next = temp
        temp.prev = self.head

        # head <-> temp

        self.size -= 1
        return x.val

    def remove_last(self):
        if self.size < 1:
            raise IndexError("No elements to remove")
        x = self.tail.prev
        temp = x.prev
        # temp <-> x <-> tail

        self.tail.prev = temp
        temp.next = self.tail

        # temp <-> tail

        self.size -= 1
        return x.val

    def remove(self, index):
        self.check_element_index(index)
        # find the Node corresponding to index
        x = self.get_node(index)
        prev = x.prev
        next = x.next
        # prev <-> x <-> next
        prev.next = next
        next.prev = prev

        self.size -= 1

        return x.val

    # ***** Get *****

    def get(self, index):
        self.check_element_index(index)
        # find the Node corresponding to index
        p = self.get_node(index)

        return p.val

    def get_first(self):
        if self.size < 1:
            raise IndexError("No elements in the list")

        return self.head.next.val

    def get_last(self):
        if self.size < 1:
            raise IndexError("No elements in the list")

        return self.tail.prev.val

    # ***** Set *****

    def set(self, index, val):
        self.check_element_index(index)
        # find the Node corresponding to index
        p = self.get_node(index)

        old_val = p.val
        p.val = val

        return old_val

    # ***** Other utility functions *****

    def size(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def get_node(self, index):
        self.check_element_index(index)
        p = self.head.next
        # TODO: Can be optimized by deciding
        # whether to traverse from head or tail
        for _ in range(index):
            p = p.next
        return p

    def is_element_index(self, index):
        return 0 <= index < self.size

    def is_position_index(self, index):
        return 0 <= index <= self.size

    # Check if the index position can contain an element
    def check_element_index(self, index):
        if not self.is_element_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    # Check if the index position can add an element
    def check_position_index(self, index):
        if not self.is_position_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    def display(self):
        print(f"size = {self.size}")
        p = self.head.next
        while p != self.tail:
            print(f"{p.val} <-> ", end="")
            p = p.next
        print("null\n")

if __name__ == "__main__":
    list = MyLinkedList()
    list.add_last(1)
    list.add_last(2)
    list.add_last(3)
    list.add_first(0)
    list.add(2, 100)

    list.display()
    # size = 5
    # 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null

javascript 🤖

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class MyLinkedList {
    // virtual head and tail nodes
    constructor() {
        this.head = new Node(null);
        this.tail = new Node(null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
    }

    // ***** Add *****

    addLast(e) {
        const x = new Node(e);
        const temp = this.tail.prev;
        // temp <-> tail
        temp.next = x;
        x.prev = temp;

        x.next = this.tail;
        this.tail.prev = x;
        // temp <-> x <-> tail
        this.size++;
    }

    addFirst(e) {
        const x = new Node(e);
        const temp = this.head.next;
        // head <-> temp
        temp.prev = x;
        x.next = temp;

        this.head.next = x;
        x.prev = this.head;
        // head <-> x <-> temp
        this.size++;
    }

    add(index, element) {
        this.checkPositionIndex(index);
        if (index === this.size) {
            this.addLast(element);
            return;
        }

        // find the Node corresponding to index
        const p = this.getNode(index);
        const temp = p.prev;
        // temp <-> p

        // new Node to be inserted
        const x = new Node(element);

        p.prev = x;
        temp.next = x;

        x.prev = temp;
        x.next = p;

        // temp <-> x <-> p

        this.size++;
    }

    // ***** Remove *****

    removeFirst() {
        if (this.size < 1) {
            throw new Error("No elements to remove");
        }
        // the existence of virtual nodes prevents us from having to consider null pointers
        const x = this.head.next;
        const temp = x.next;
        // head <-> x <-> temp
        this.head.next = temp;
        temp.prev = this.head;

        // head <-> temp

        this.size--;
        return x.val;
    }

    removeLast() {
        if (this.size < 1) {
            throw new Error("No elements to remove");
        }
        const x = this.tail.prev;
        const temp = x.prev;
        // temp <-> x <-> tail

        this.tail.prev = temp;
        temp.next = this.tail;

        // temp <-> tail

        this.size--;
        return x.val;
    }

    remove(index) {
        this.checkElementIndex(index);
        // find the Node corresponding to index
        const x = this.getNode(index);
        const prev = x.prev;
        const next = x.next;
        // prev <-> x <-> next
        prev.next = next;
        next.prev = prev;

        this.size--;

        return x.val;
    }

    // ***** Get *****

    get(index) {
        this.checkElementIndex(index);
        // find the Node corresponding to index
        const p = this.getNode(index);

        return p.val;
    }

    getFirst() {
        if (this.size < 1) {
            throw new Error("No elements in the list");
        }

        return this.head.next.val;
    }

    getLast() {
        if (this.size < 1) {
            throw new Error("No elements in the list");
        }

        return this.tail.prev.val;
    }

    // ***** Set *****

    set(index, val) {
        this.checkElementIndex(index);
        // find the Node corresponding to index
        const p = this.getNode(index);

        const oldVal = p.val;
        p.val = val;

        return oldVal;
    }

    // ***** Other utility functions *****

    size() {
        return this.size;
    }

    isEmpty() {
        return this.size === 0;
    }

    getNode(index) {
        this.checkElementIndex(index);
        let p = this.head.next;
        // TODO: Can be optimized by deciding
        // whether to traverse from head or tail
        for (let i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    isElementIndex(index) {
        return index >= 0 && index < this.size;
    }

    isPositionIndex(index) {
        return index >= 0 && index <= this.size;
    }

    // Check if the index position can contain an element
    checkElementIndex(index) {
        if (!this.isElementIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    // Check if the index position can add an element
    checkPositionIndex(index) {
        if (!this.isPositionIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    display() {
        console.log(`size = ${this.size}`);
        let p = this.head.next;
        let str = "";
        while (p !== this.tail) {
            str += `${p.val} <-> `;
            p = p.next;
        }
        console.log(str + "null\n");
    }
}

// Testing the MyLinkedList class
const list = new MyLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addFirst(0);
list.add(2, 100);

list.display();
// size = 5
// 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null

golang 🤖

package main

import (
	"errors"
	"fmt"
)

type Node struct {
	val  interface{}
	next *Node
	prev *Node
}

type MyLinkedList struct {
	head *Node
	tail *Node
	size int
}

// virtual head and tail nodes
func NewMyLinkedList() *MyLinkedList {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head
	return &MyLinkedList{head: head, tail: tail, size: 0}
}

// ***** Add *****

func (list *MyLinkedList) AddLast(e interface{}) {
	x := &Node{val: e}
	temp := list.tail.prev
	// temp <-> tail
	temp.next = x
	x.prev = temp

	x.next = list.tail
	list.tail.prev = x
	// temp <-> x <-> tail
	list.size++
}

func (list *MyLinkedList) AddFirst(e interface{}) {
	x := &Node{val: e}
	temp := list.head.next
	// head <-> temp
	temp.prev = x
	x.next = temp

	list.head.next = x
	x.prev = list.head
	// head <-> x <-> temp
	list.size++
}

func (list *MyLinkedList) Add(index int, element interface{}) {
	list.checkPositionIndex(index)
	if index == list.size {
		list.AddLast(element)
		return
	}

	// find the Node corresponding to index
	p := list.getNode(index)
	temp := p.prev
	// temp <-> p

	// new Node to be inserted
	x := &Node{val: element}

	p.prev = x
	temp.next = x

	x.prev = temp
	x.next = p

	// temp <-> x <-> p

	list.size++
}

// ***** Remove *****

func (list *MyLinkedList) RemoveFirst() (interface{}, error) {
	if list.size < 1 {
		return nil, errors.New("no elements to remove")
	}
	// the existence of virtual nodes prevents us from having to consider null pointers
	x := list.head.next
	temp := x.next
	// head <-> x <-> temp
	list.head.next = temp
	temp.prev = list.head

	// head <-> temp

	list.size--
	return x.val, nil
}

func (list *MyLinkedList) RemoveLast() (interface{}, error) {
	if list.size < 1 {
		return nil, errors.New("no elements to remove")
	}
	x := list.tail.prev
	temp := x.prev
	// temp <-> x <-> tail

	list.tail.prev = temp
	temp.next = list.tail

	// temp <-> tail

	list.size--
	return x.val, nil
}

func (list *MyLinkedList) Remove(index int) (interface{}, error) {
	list.checkElementIndex(index)
	// find the Node corresponding to index
	x := list.getNode(index)
	prev := x.prev
	next := x.next
	// prev <-> x <-> next
	prev.next = next
	next.prev = prev

	list.size--

	return x.val, nil
}

// ***** Get *****

func (list *MyLinkedList) Get(index int) (interface{}, error) {
	list.checkElementIndex(index)
	// find the Node corresponding to index
	p := list.getNode(index)

	return p.val, nil
}

func (list *MyLinkedList) GetFirst() (interface{}, error) {
	if list.size < 1 {
		return nil, errors.New("no elements in the list")
	}

	return list.head.next.val, nil
}

func (list *MyLinkedList) GetLast() (interface{}, error) {
	if list.size < 1 {
		return nil, errors.New("no elements in the list")
	}

	return list.tail.prev.val, nil
}

// ***** Set *****

func (list *MyLinkedList) Set(index int, val interface{}) (interface{}, error) {
	list.checkElementIndex(index)
	// find the Node corresponding to index
	p := list.getNode(index)

	oldVal := p.val
	p.val = val

	return oldVal, nil
}

// ***** Other utility functions *****

func (list *MyLinkedList) Size() int {
	return list.size
}

func (list *MyLinkedList) IsEmpty() bool {
	return list.size == 0
}

func (list *MyLinkedList) getNode(index int) *Node {
	list.checkElementIndex(index)
	p := list.head.next
	// TODO: Can be optimized by deciding whether to traverse from head or tail based on index
	for i := 0; i < index; i++ {
		p = p.next
	}
	return p
}

func (list *MyLinkedList) isElementIndex(index int) bool {
	return index >= 0 && index < list.size
}

func (list *MyLinkedList) isPositionIndex(index int) bool {
	return index >= 0 && index <= list.size
}

// Check if the index position can contain an element
func (list *MyLinkedList) checkElementIndex(index int) {
	if !list.isElementIndex(index) {
		panic(fmt.Sprintf("Index: %d, Size: %d", index, list.size))
	}
}

// Check if the index position can add an element
func (list *MyLinkedList) checkPositionIndex(index int) {
	if !list.isPositionIndex(index) {
		panic(fmt.Sprintf("Index: %d, Size: %d", index, list.size))
	}
}

func (list *MyLinkedList) Display() {
	fmt.Printf("size = %d\n", list.size)
	p := list.head.next
	for p != list.tail {
		fmt.Printf("%v <-> ", p.val)
		p = p.next
	}
	fmt.Println("null\n")
}

func main() {
	list := NewMyLinkedList()
	list.AddLast(1)
	list.AddLast(2)
	list.AddLast(3)
	list.AddFirst(0)
	list.Add(2, 100)

	list.Display()
	// size = 5
	// 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null
}

Singly Linked List Code Implementation