Forem: Guilherme Henrique

Linked Lists Simplified: A Guide to Understanding and Implementing

Guilherme Henrique — Sun, 01 Sep 2024 15:46:15 +0000

A linked list is a data structure that represents a sequence of data elements of the same type. Each data element is stored in a node, which contains the element itself and the address of the next node, that's why it's called a Linked list because each node is linked to the next one.

Now, let's take a look at a Java code example representing a simple linked list implementation:

// Node.java

public class Node<T> {
    private Node<T> next;
    private T value;

    public Node(T value) {
        this.value = value;
        this.next = null;
    }

    public Node next() {
        return this.next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public T value() {
        return this.value;
    }

    public void setValue(T value) {
        this.value = value;
    }
}

// LinkedList.java

public class LinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int length;

    public LinkedList() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    public boolean isEmpty() {
        return this.length == 0;
    }

    public void add(T element) {
        Node<T> node = new Node<>(element);

        if (this.isEmpty()) {
            this.head = node;
            this.tail = node;
            this.length++;

            return;
        }

        this.tail.setNext(node);
        this.tail = node;
        this.length++;
    }

    public void remove(T value) {
        if (this.isEmpty()) {
            return;
        }

        if (value.equals(this.head.value()) {
            this.head = this.head.next();

            if (this.head == null) {
                this.tail = null;
            }

            this.length--;
            return;
        }

        Node<T> current = this.head;
        Node<T> previous = null;

        // Find the element
        while (current != null && !value.equals(current.value()) {
            previous = current;
            current = current.next();
        }

        // Element not found
        if (current == null) {
            return;
        }

        // "removing" the element
        previous.setNext(current.next());

        // "removing" the last element
        if (current == this.tail) {
            this.tail = previous;
        }

        this.length--;
    }
}

In the example above we have a simple LinkedList implementation, first we have a Node class with 2 properties:

next: A Node representing the next node of the list
value: The value stored in the list

In the LinkedList class we have 3 properties:

head: The Node representing the first element in the list
tail: The Node representing the last element in the list
length: The list length

And the two main methods:

add(T element): This method checks if the list is empty. If it is, it sets the new node as both the head and the tail of the list and increments the length by 1. If the list is not empty, it appends the new node to the end of the list. In this case, the next pointer of the current tail is updated to reference the new node, and the tail is updated to the new node, effectively making it the new end of the list.

remove(T element): This method removes an element from the list by its value. It does not actually delete the node but instead adjusts the links between nodes to "ignore" the node with the target value.

First, it checks if the element to be removed is the head of the list. If so, it updates the head to the next node. If the new head is null, this means the list is now empty, and the tail is also set to null.

If the element is not the head, the method searches for the element in the list by comparing values in a loop. If the element is not found (i.e., current becomes null), the method simply returns. If the element is found, it updates the next pointer of the previous node to skip over the node being removed, thereby effectively removing it from the list. Finally, if the removed node was the tail, the tail is updated to the previous node. The length of the list is then decremented by 1.

Stacks in Action: A Dive into the Concept and Implementation

Guilherme Henrique — Sun, 12 May 2024 19:47:21 +0000

A stack is a data structure that allows the addition and removal of elements with a specific rule: the last element to be added is the first one to be removed. This rule follows the LIFO (Last-In, First-Out) order, which means that the last item to enter the stack is the first to leave. Stacks are similar to a real-life stack of plates, where the plate placed on top of the stack is the first to be removed.

Now, let's take a look at a Java code example representing a simple stack implementation:

import java.util.List;
import java.util.ArrayList;
import java.util.function.Consumer;

public class Stack<T> {
    private int top;
    private int length;
    private List<T> data;

    public Stack() {
        this.top = -1;
        this.length = 0;
        this.data = new ArrayList<T>();
    }

    public boolean isEmpty() {
        return this.length == 0;
    }

    public void push(T element) {
        this.top++;
        this.length++;
        this.data.add(element);
    }

    public T getTop() {
        if (this.isEmpty()) {
            throw new RuntimeException("empty stack");
        }

        return this.data.get(top);
    }

    public T pop() {
        if (this.isEmpty()) {
            throw new RuntimeException("empty stack");
        }

        T element = this.data.remove(top);

        this.top--;
        this.length--;
        return element;
    }

    public void forEach(Consumer<T> consumer) {
        for (int i = this.top; i >= 0; i--) {
            consumer.accept(this.data.get(i));
        }
    }
}

In the code above we have a simple stack structure with 3 properties:

top: The index of the top element.
length: The length.
data: A list of a generic type to store the data.

And we have 3 main methods:

push: The top position will be the next one, the length will be incremented by 1 and the new element will be added to the top of the stack.
pop: This method checks if the stack is empty. If it is, an exception is thrown indicating that the stack is empty. If it is not empty, it retrieves the top element, decrements the top index and the length by 1, and then returns the removed top element.

push usage example:

Stack<Integer> stack = new Stack();
stack.push(10); // index 0
stack.push(20); // index 1
stack.push(30); // index 2
// the top is 2

pop usage example:

Stack<Integer> stack = new Stack();
stack.push(10); // index 0
stack.push(20); // index 1
stack.push(30); // index 2
// the top is 2
Integer removed = stack.pop();
// after pop top is 1

A Comprehensive Guide to Queue Data Structure

Guilherme Henrique — Mon, 06 May 2024 21:39:55 +0000

A queue is a data structure that allows the addition and removal of elements with a specific rule: the first element to be added is the first one to be removed. This rule follows the FIFO (First-In, First-Out) order, which means that the first item to enter the queue is also the first to leave. Queues are similar to a real-life queue of people, where the person who arrives first is the one to be served first.

Now, let's look at a Java code example that represents a simple implementation of a queue:

import java.util.LinkedList;
import java.util.List;

public class Queue<T> {
    private List<T> data;
    private int length;

    public Queue() {
        this.data = new LinkedList<>();
        this.length = 0;
    }

    public void enqueue(T value) {
        this.data.add(value);
        this.length++;
    }

    public T dequeue() {
        if (this.length == 0) {
            throw new RuntimeException("Empty queue");
        }

        this.length--;
        return this.data.remove(0);
    }
}

In the code above we have a simple queue structure with 2 properties:

data: A List to store the queue data
length: The queue length

And we have 2 main methods:

enqueue: This method adds the new element to the List and increments the length variable by 1.
dequeue: This method verifies if the queue is empty if it's true an exception will be thrown saying the queue is empty, if it's false the length variable is decreased by 1, then the first element of the list is removed and returned.

enqueue Usage example:

Queue<Integer> queue = new Queue();
queue.enqueue(10); // index 0
queue.enqueue(20); // index 1
queue.enqueue(30); // index 2

dequeue Usage example:

Queue<Integer> queue = new Queue();
queue.enqueue(10); // index 0
queue.enqueue(20); // index 1
queue.enqueue(30); // index 2

queue.dequeue();
// after dequeue the first element is removed