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 singly linked list.
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 singly linked list.

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 doubly linked 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:

A circular singly linked list.

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

A circular doubly 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
}

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

Comments

Post a Comment

Popular posts from this blog

Archunit test

  ArchUnit  integrates nicely with the  JUnit  test framework, and so, they are typically used together.  All we have to do is add the  archunit-junit 5  dependency to match our  JUnit  version: < dependency > < groupId > com.tngtech.archunit </ groupId > < artifactId > archunit-junit5 </ artifactId > < version > 0.14.1 </ version > < scope > test </ scope > </ dependency > Step 1: The first step is to create a set of Java classes that will be checked for rules violations . We do this by instantiating the  ClassFileImporter  class and then using one of its  importXXX()  methods: JavaClasses jc = new ClassFileImporter () .importPackages( "com.baeldung.archunit.smurfs" ); Step 2:  Let’s try to implement the first rule defined above using this API. We’ll use the  classes()  method as our anchor and add additional constraints ...
Read more

Hexagonal Architecture

Image
  Hexagonal architecture is a model of  designing software applications around domain logic  to isolate it from external factors. The domain logic is specified in a business core, which we’ll call the inside part, with the rest being outside parts.  Access to domain logic from the outside is available through  ports  and  adapters .  here we divide our application into three layers:  application (outside), domain (inside), and infrastructure (outside): Through  the application layer, the user or any other program interacts  with the application. This area should contain things like user interfaces, RESTful controllers, and JSON serialization libraries. It includes anything  that exposes entry to our application, and orchestrates the execution of domain logic. In the domain layer, we keep the code that touches and implements business logic . This is the core of our application. This layer should be isolated from both the applica...
Read more

visitor design pattern

Image
  The Visitor design pattern is a  behavioral pattern  that allows you to add new operations to a group of related classes without modifying their structures. Real-World Example of Visitor Design Pattern A simple example of the Visitor design pattern is in an online shopping cart. Imagine you have different items like books, electronics, and clothing. Each item can accept a visitor that performs actions like calculating the total price or applying discounts. This way, you can add new features without changing the item classes, making the system easier to maintain and update. UML Class Diagram of Visitor design pattern Components of Visitor Design Pattern The Visitor design pattern consists of several key components that work together to enable its functionality. Here’s a breakdown of these components: Visitor Interface : This interface declares a visit method for each type of element in the object structure. Each method is designed to handle a specific element type. Concr...
Read more