LinkedList Implementation and Basic Operations

This is the first blog on linked lists that contains implementations in Java and introduces basic operation such as add, get and delete. You can also read about problems and their solutions on linked lists on LinkedList Common Problems and Solutions post.

Linked List is a sequence of data that are connected by links. Each list item is commonly referred as Node. Every node stores certain data and a link to the next element. On the other hand, Linked lists can also have two links (previous and next) to optimize some operations. They are called doubly linked lists.

Here is a simple illastration of singly linked lists.

and doubly linked list

Here is simple implementation of singly linked list in Java

class LinkedList<E> {

    private Node head; // the first element
    private Node tail; // the last element
    int size;

    public void add(E element) {
        // tail and head are the same node when list has only one item
        if (head == null){
            head = tail = new Node(element);
        }else {
        //assign new node to next of tail and make tail the last element
            tail.next = new Node(element);
            tail = tail.next;
        }
        size++;
    }

    public E get(int index) {
        if (index >= size && index < 0) // check boundaries
            throw new NoSuchElementException();

        // find element at given index
        Node node = head;
        for (int i = 0; i < index; i++)
            node = node.next;

        return node.elem;
    }

    public boolean delete(E element) {
        Node temp = new Node(null, head); // dummy element to avoid if checks
        Node dummy = temp;
        while (temp.next != null) {
            if (temp.next.elem.equals(element)) {
                // if found node is last node of the list, need to change tail
                if (temp.next == tail) tail = temp;
                temp.next = temp.next.next;
                // if found node is first node if the list, need to change head
                head = dummy.next;
                size--;
                return true;
            }
            temp = temp.next;
        }

        return false;
    }

    // wrapper class for list elements
    private class Node {
        E elem;
        Node next;
        public Node(E elem) {
            this.elem = elem;
        }
        public Node(E el, Node node) {
            this.elem = el;
            this.next = node;
        }
    }
  }

You can add addFirst and getFirst, addLast and getLast methods by changing references of head and tail respectively. They are easy and constant operations.

And here is implementaion of doubly linked list. Every node stores element data and two links: prev and next.

class DoublyLinkedList<E> {
    private Node head; // the first element
    private Node tail; // the last element
    int size;

    public void add(E element) {
        if (element == null) throw new AssertionError();

        // tail and head are the same node when list has only one item
        if (head == null) {
            head = tail = new Node(element);
        } else {
            //assign new node to next of tail and make tail the last element
            tail.next = new Node(element, tail, null);
            tail = tail.next;
        }
        size++;
    }
    public boolean isEmpty() {
         return size == 0;
    }
    public int getSize() {
         return size;
    }
    public E get(int index) {
        if (index >= size && index < 0) // check boundaries
            throw new NoSuchElementException();

        // find element at given index
        Node node = head;
        for (int i = 0; i < index; i++)
             node = node.next;

        return node.elem;
    }

    public boolean delete(E element) {

        Node temp = head;
        while (temp != null && !temp.elem.equals(element)) {
            temp = temp.next;
        }
        // no node with given element is found
        if (temp == null) return false;

        size--;

        // if found node is head of the list, need to change to next element
        if (temp == head) {
            head = head.next;
            return true;
        }
        // if found node is last node of the list, need to change tail
        if (temp == tail) {
            tail = temp.prev;
            return true;
        }
        // change links
        temp.prev.next = temp.next;
        temp.next.prev = temp.prev;

        return true;
    }

    // wrapper class for list elements
    private class Node {
        E elem;
        Node next;
        Node prev;

        public Node(E elem) {
             this.elem = elem;
        }
        public Node(E elem, Node prev, Node next) {
            this.elem = elem;
            this.next = next;
            this.prev = prev;
        }
    }
   }

This is the first blog about linked lists, you can read LinkedList Advanced Operations blog for recursion, reversing and some other operation imlementations.