Home



2019/05 - DS&A #2: Linked Lists

Hey folks,

Continuing on from our last introductory post this post will be about a basic data structure: The Linked List (If you are not already intrigued, you aren't going to be).

The theory behind a Linked List is that you're creating a data structure by giving each node/object/element in the (Linked) list a pointer to the next node in the queue. We're storing all of the nodes in memory, telling them where they are in the list based on which node is "next" to or "previous" to each of them, and keeping a counter so we can tell how many nodes we're storing. A decent metaphor for this would be a train (Your linked list) that consists of carriages (Your nodes) where you can only move one carriage up, but not return back to any previous carriages. Also the train is store on a computer, so it is a mere concept that doesn't even allow for windows, passengers, or anything else that would make sense.

There is another type of LinkedList, called a Doubly Linked List, which is essentially the same as a Linked List, but where every node has another pointer back to it's previous node. So unlike in the above example, you CAN go back to previous carriages! However your train is still trapped in your computer forever, in a modern nightmare similar to the Henry episode of Thomas the Tank Engine. You can always copy it to another computer, but it'll still exist in its hellish, tormented, windowless Eclipse project.

Getting back to Linked Lists, your can find my code examples here if you want to get an idea of what these data structures should look like in your IDE.

 

You basically have a POJO that stores info (Your node):

public class Node {
    
    int value = 0;
    Node next = null;
    
    public Node(int value) {
        this.value = value;
    }
    
    public String toString() {
        return "Value: " + value;
    }

}

 

And a Linked List that traverses a collection of these nodes (Thought not a collection in the sense that it is a Java API collection, just so we're clear). I'm going to break up the Linked List code into sections because it's much longer than the Node code:


    Node head;
    Node tail;
    
    int count = 0;


    
The head is the front/top of the list (the front carriage of the train), the tail is the back/end of the list (end of the train) and the count is the number of nodes (Or carriages).

    private void assignFirstNode(Node firstNode) {
        head = firstNode;
        tail = firstNode;
        
    }


    
The above method assigns the first element to our "list". We could just put this code into a generic "add" method and not have three methods for adding nodes, but I'm trying to keep the theory clear here. 

    public void addToFront(Node newFrontNode) {
        if(head == null && tail == null) {
            assignFirstNode(newFrontNode);
        }
        else {
            Node oldHead = head;
            newFrontNode.next = oldHead;
            head = newFrontNode;
        }
        
        count++;
    }

 

We can also add a new carriage to the end of the train, as opposed to the front of the train:    

public void addToEnd(Node newEndNode) {
        if(head == null && tail == null) {
            assignFirstNode(newEndNode);
        }
        else {
            Node oldTail = tail;
            oldTail.next = newEndNode;
            head = newEndNode;
        }
        
        count++;
    }

 

Removal works the same way for both ends, lowering the count and reassigning the head/tail (Front/end carriages of train):

    public void removeFromFront() {
        if(count>0) {
            head = head.next;
            count--;    
        }
    }
    
    public void removeFromEnd() {
        if(count>0) {
            Node temp = head;
            while(temp.next.next != null) {
              
                temp = temp.next;
            }
            tail = temp;
            count--;    
        }
    }

And that's basically it for the basics! Linked Lists and Doubly Linked Lists are fairly straight-forwards concepts. I was once asked to compare the two in a phone interview before, so it is very possible that this information will be of use to you too.