A small introduction to Linked Lists

A linked list is a linear collection of data elements, which are connected together via links. Let’s have a quick look at it!

A linked list is a sequence of data items, just like an array. The main difference between an array and a linked list is while an array needs a big block of memory to store the objects, the elements in a linked list are totally separate objects in memory and are connected through links.

The elements of a linked list are referred to as nodes and each node has a reference (or “pointer”) to the next node. We need to keep track of where the list begins and it is usually done with a pointer called the head. It also can be useful to have a reference to the end of the list called the tail. The next pointer of the last node is nil, just like the previous pointer of the first node.

``| node 0 |--->| node 1 |--->| node 2 |--->| node 3 |``

We can also have something called doubly linked list, where each node has a pointer to the previous node.

A singly linked list uses less memory than a doubly linked list because it does not need to store all previous pointers. However, with a singly linked list, if we need to find the previous pointer of any node, we have to start at the head of the list and iterate through the entire list until we get to the right node.

Most operations on a linked list have O(n) time, and so linked lists are generally slower than arrays. The main reason for that is we can’t access directly to a specific node. If we don’t have a reference to that specific node already, we have to start at the head (or at the tail) of the list and work our way down (or up) to the desired node by following the next pointers (our previous).

Nevertheless, once we have a reference to a node, operations like insertion and deletion are really fast.

Let’s have a really simple example written in _Java _of a singly list implementation. For the sake of our example, we will work with books and we will define everything as public so getters and setters aren’t needed.

First of all, we define a LinkList class like so:

``public class LinkList {        public Link firstLink;        LinkList() {        firstLink = null;    }        public boolean isEmpty() {        return(firstLink == null);    }        public void insertFirstLink(String bookName) {                Link newLink = new Link(bookName);        newLink.next = firstLink;        firstLink = newLink;            }        public Link removeFirst() {                Link linkReference = firstLink;                if (!isEmpty()) {            firstLink = firstLink.next;        } else {            System.out.println("Empty LinkedList");        }                return linkReference;            }        public void display() {                Link theLink = firstLink;                while(theLink != null) {                        theLink.display();            System.out.println("Next link: " + theLink.next);            theLink = theLink.next;            System.out.println();                    }            }        public Link find(String bookName) {                Link theLink = firstLink;                if (!isEmpty()) {                        while(theLink.bookName != bookName ) {                                if (theLink.next == null) {                    return null;                } else {                    theLink = theLink.next;                }                            }                    } else {            System.out.println("Empty LinkedList");        }                return theLink;            }        public Link removeLink(String bookName) {                Link currentLink = firstLink;        Link previousLink = firstLink;                while(currentLink.bookName != bookName ) {                        if (currentLink.next == null) {                return null;            } else {                previousLink = currentLink;                currentLink = currentLink.next;            }                    }                if (currentLink == firstLink) {            firstLink = firstLink.next;        } else {            previousLink.next = currentLink.next;        }                return currentLink;            }    }``

Then we define a Link class and do some basic operations in the main just to illustrate our example:

``public class Link {        public String bookName;        public Link next;        public Link(String bookName) {        this.bookName = bookName;    }        public void display() {        System.out.println(bookName);    }        public String toString() {        return bookName;    }        public static void main(String[] args ) {                LinkList theLinkedList = new LinkList();                theLinkedList.insertFirstLink("2001 A Space Odyssey");        theLinkedList.insertFirstLink("Twenty Thousand Leagues Under the Sea");        theLinkedList.insertFirstLink("The Lord of the Rings");        theLinkedList.insertFirstLink("1984";                theLinkedList.display();        theLinkedList.removeFirst();        theLinkedList.display();                System.out.println(theLinkedList.find("The Lord of the Rings").bookName + " was found");        theLinkedList.removeLink("The Lord of the Rings");        theLinkedList.display();            }    }``