Data structure and Algorithyms

 

Linked Lists

A linked list consists of nodes with some sort of data, and a pointer, or link, to the next node.

A big benefit with using linked lists is that nodes are stored wherever there is free space in memory, the nodes do not have to be stored contiguously right after each other like elements are stored in arrays. Another nice thing with linked lists is that when adding or removing nodes, the rest of the nodes in the list do not have to be shifted.

Types of Linked Lists

There are three basic forms of linked lists:

1. Singly linked lists
2. Doubly linked lists
3. Circular linked lists

---

A singly linked list is the simplest kind of linked lists. It takes up less space in memory because each node has only one address to the next node, like in the image below.

---

A doubly linked list has nodes with addresses to both the previous and the next node, like in the image below, and therefore takes up more memory. But doubly linked lists are good if you want to be able to move both up and down in the list.

---

A circular linked list is like a singly or doubly linked list with the first node, the "head", and the last node, the "tail", connected.

In singly or doubly linked lists, we can find the start and end of a list by just checking if the links are null. But for circular linked lists, more complex code is needed to explicitly check for start and end nodes in certain applications.

Circular linked lists are good for lists you need to cycle through continuously.

The image below is an example of a singly circular linked list:

The image below is an example of a doubly circular linked list:

 singly linked list

static class Node {

        int data;

        Node next;

        Node(int data) {

            this.data = data;

            this.next = null;

        }

doubly linked list 

static class Node {

        int data;

        Node next;

        Node prev;

        Node(int data) {

            this.data = data;

            this.next = null;

            this.prev = null;

        }

circular can be maintained in link:

public class Main {

    static class Node {

        int data;

        Node next;

        Node prev;

        Node(int data) {

            this.data = data;

        }

    }

    public static void main(String[] args) {

        Node node1 = new Node(3);

        Node node2 = new Node(5);

        Node node3 = new Node(13);

        Node node4 = new Node(2);

        node1.next = node2;

        node1.prev = node4;  // Circular link

        node2.prev = node1;

        node2.next = node3;

        node3.prev = node2;

        node3.next = node4;

        node4.prev = node3;

        node4.next = node1;  // Circular link

        System.out.println("\nTraversing forward:");

        Node currentNode = node1;

        Node startNode = node1;

        System.out.print(currentNode.data + " -> ");

        currentNode = currentNode.next;

        while (currentNode != startNode) {

            System.out.print(currentNode.data + " -> ");

            currentNode = currentNode.next;

        }

        System.out.println("...");  // Indicating the list loops back

}

DSA Linked Lists Types

Basic things we can do with linked lists are:

1. Traversal
2. Remove a node
3. Insert a node
4. Sort

1. Traversal

public static void traverseAndPrint(Node head) {

        Node currentNode = head;

        while (currentNode != null) {

            System.out.print(currentNode.data + " -> ");

            currentNode = currentNode.next;

        }

        System.out.println("null");

    }

public class Main {

    

    static class Node {

        int data;

        Node next;

        Node(int data) {

            this.data = data;

            this.next = null;

        }

    }

    public static void traverseAndPrint(Node head) {

        Node currentNode = head;

        while (currentNode != null) {

            System.out.print(currentNode.data + " -> ");

            currentNode = currentNode.next;

        }

        System.out.println("null");

    }

    public static void main(String[] args) {

        Node node1 = new Node(7);

        Node node2 = new Node(11);

        Node node3 = new Node(3);

        Node node4 = new Node(2);

        Node node5 = new Node(9);

        node1.next = node2;

        node2.next = node3;

        node3.next = node4;

        node4.next = node5;

        traverseAndPrint(node1);

    }

}

7 -> 11 -> 3 -> 2 -> 9 -> null

Find min value:

 public static int findLowestValue(Node head) {
        int minValue = head.data;
        Node currentNode = head.next;
        while (currentNode != null) {
            if (currentNode.data < minValue) {
                minValue = currentNode.data;
            }
            currentNode = currentNode.next;
        }
        return minValue;
    }

delete specific node:

 public static Node deleteSpecificNode(Node head, Node nodeToDelete) {

        if (head == nodeToDelete) {

            return head.next;

        }

        Node currentNode = head;

        while (currentNode.next != null && currentNode.next != nodeToDelete) {

            currentNode = currentNode.next;

        }

        if (currentNode.next == null) {

            return head;

        }

        currentNode.next = currentNode.next.next;
        return head;
    }

insert a node

public static Node insertNodeAtPosition(Node head, Node newNode, int position) {

        if (position == 1) {

            newNode.next = head;

            return newNode;

        }

        Node currentNode = head;

        for (int i = 1; i < position - 1 && currentNode != null; i++) {

            currentNode = currentNode.next;

        }

        if (currentNode != null) {

            newNode.next = currentNode.next;

            currentNode.next = newNode;

        }

        return head;

    }

Stacks

A stack is a data structure that can hold many elements.

3

2

3

1

Result:

Think of a stack like a pile of pancakes.

In a pile of pancakes, the pancakes are both added and removed from the top. So when removing a pancake, it will always be the last pancake you added. This way of organizing elements is called LIFO: Last In First Out.

Basic operations we can do on a stack are:

• Push: Adds a new element on the stack.
• Pop: Removes and returns the top element from the stack.
• Peek: Returns the top element on the stack.
• isEmpty: Checks if the stack is empty.
• Size: Finds the number of elements in the stack.

Stack Implementation using Arrays

public class Main {

    public static void main(String[] args) {

        Stack myStack = new Stack(10);

        myStack.push('A');

        myStack.push('B');

        myStack.push('C');

        // Print initial stack

        System.out.print("Stack: ");

        myStack.printStack();

        System.out.println("Pop: " + myStack.pop());

        System.out.println("Peek: " + myStack.peek());

        System.out.println("isEmpty: " + myStack.isEmpty());

        System.out.println("Size: " + myStack.size());

    }

}

class Stack {

    char[] stack;

    int top;

    int capacity;

    public Stack(int capacity) {

        this.capacity = capacity;

        this.stack = new char[capacity];

        this.top = -1;

    }

    public void push(char element) {

        if (top == capacity - 1) {

            System.out.println("Stack is full");

            return;

        }

        stack[++top] = element;

    }

    public char pop() {

        if (isEmpty()) {

            System.out.println("Stack is empty");

            return ' ';

        }

        return stack[top--];

    }

    public char peek() {

        if (isEmpty()) {

            System.out.println("Stack is empty");

            return ' ';

        }

        return stack[top];

    }

    public boolean isEmpty() {

        return top == -1;

    }

    public int size() {

        return top + 1;

    }

    public void printStack() {

        for (int i = 0; i <= top; i++) {

            System.out.print(stack[i] + " ");

        }

        System.out.println();

    }

}

Stack Implementation using Linked Lists

public class Main {

    public static void main(String[] args) {

        Stack myStack = new Stack();

        

        myStack.push('A');

        myStack.push('B');

        myStack.push('C');

        System.out.println("Pop: " + myStack.pop());

        System.out.println("Peek: " + myStack.peek());

        System.out.println("isEmpty: " + myStack.isEmpty());

        System.out.println("Size: " + myStack.size());

    }

}

class Node {

    char value;

    Node next;

    Node(char value) {

        this.value = value;

        this.next = null;

    }

}

class Stack {

    private Node head;

    private int size;

    public Stack() {

        this.head = null;

        this.size = 0;

    }

    public void push(char value) {

        Node newNode = new Node(value);

        if (head != null) {

            newNode.next = head;

        }

        head = newNode;

        size++;

    }

    public char pop() {

        if (isEmpty()) {

            return ' ';

        }

        char popped = head.value;

        head = head.next;

        size--;

        return popped;

    }

    public char peek() {

        if (isEmpty()) {

            return ' ';

        }

        return head.value;

    }

    public boolean isEmpty() {

        return size == 0;

    }

    public int size() {

        return size;

    }

}

//Java