Linked lists

In today's post, I'm going to talk about the single linked list data structure, so let's begin.

What is a linked list

A Linked List basically is a linear data structure consisting of a collection of elements (nodes) in sequence, nodes don't store in order in the memory, instead each node points to another memory reference.

Implementation

Let's start by implementing the Node class, for our node class we only need two properties for our class, value and next, Value will currently hold the node value and the Next property will contain the next node location.

public class Node {
        public int data;
        public Node next;

        public Node(int data) {
            this.data = data;
        }
    }

public class MyLinkedList {
    Node head;

    public void appendFirst(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node newNode = new Node(data);
        newNode.next = this.head;

        this.head = newNode;
    }

    public void appendLast(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }

        Node currentNode = this.head;
        while (currentNode != null) {
            currentNode = currentNode.next;
        }

        currentNode.next = new Node(data);
    }

    public void removeFirst() {
        if (this.head == null) return;

        this.head = this.head.next;
    }

    public void removeLast() {
        if (this.head == null) return;

        if (this.head.next == null) {
            this.head = null;
            return;
        }

        Node currentNode = this.head;
        while (currentNode.next.next != null) {
            currentNode = currentNode.next;
        }

        currentNode.next = null;
    }

    public void traversal() {
        Node currentNode = this.head;
        while (currentNode != null) {
            currentNode = currentNode.next;
        }
    }
}

In a nutshell, this is the Linked List data structure, when is viable to use them? When we want to add to the beginning of the list since is an O(1) we only need to change next pointer.