Languages
[Edit]
EN

Java - delete node from double linked list (custom implementation)

12 points
Created by:
AnnLen
9180

1. Overview

In this post we will see how to implement algorithm to correctly delete node from double linked list. Below we have 2 implementations how to remove node:

  • First one with node based on Integer
  • Second one with generic Node and usage example based on String

When we unlink node from double linked list, we need to consider 4 cases:

  • when list is empty (size is 0 and first and last node is null)
  • when we need to delete first node (node that have null as previous node)
  • when we need to delete middle node (node that has previous and next node)
  • when we need to delete last node (node that have null as next node)

2. Delete node code example

Below we have java implementation with Node with Integer as item of double linked list with unlink method which will remove node from our list. This implementation is without generics to have this example as simple as possible. Generic implementation is in next part of this post.

package com.dirask;

public class DoubleLinkedList {
    Node first;
    Node last;
    int size;

    public Node addLast(Integer item) {
        Node tmpLast = last;
        Node newNode = new Node(tmpLast, item, null);
        last = newNode; // assign new node as last
        if (tmpLast == null) {
            first = newNode; // if list is empty
        } else {
            // take care that the last node will be linked
            tmpLast.next = newNode;
        }
        size++;
        return newNode;
    }

    public Integer unlink(Node unlink) {
        Integer item = unlink.item;
        Node prev = unlink.prev;
        Node next = unlink.next;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            unlink.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            unlink.next = null;
        }

        unlink.item = null;
        size--;
        return item;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        if (first != null) {
            return first.printForward();
        }
        return "List is empty";
    }

    private static class Node {
        Node prev;
        Integer item;
        Node next;

        public Node(Node prev, Integer item, Node next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }

        public String printForward() {
            if (next != null) {
                return item + " -> " + next.printForward();
            }
            return String.valueOf(item);
        }
    }

    private static void print(DoubleLinkedList list) {
        System.out.println("size: " + list.getSize() + " | list: " + list.toString());
    }

    public static void main(String[] args) {

        DoubleLinkedList list = new DoubleLinkedList();
        Node node1 = list.addLast(1);
        Node node2 = list.addLast(2);
        Node node3 = list.addLast(3);

        print(list);

        list.unlink(node1);
        print(list);

        list.unlink(node2);
        print(list);

        list.unlink(node3);
        print(list);
    }
}

Output:

size: 3 | list: 1 -> 2 -> 3
size: 2 | list: 2 -> 3
size: 1 | list: 3
size: 0 | list: List is empty

3. Delete node - generic implementation

Below we have java generic implementation of double linked list with unlink method which will remove node from our list.

package com.dirask;

public class DoubleLinkedList<E> {
    private Node<E> first;
    private Node<E> last;
    private int size;

    public Node<E> addLast(E item) {
        Node<E> tmpLast = last;
        Node<E> newNode = new Node<>(tmpLast, item, null);
        last = newNode; // assign new node as last
        if (tmpLast == null) {
            first = newNode; // if list is empty
        } else {
            // take care that the last node will be linked
            tmpLast.next = newNode;
        }
        size++;
        return newNode;
    }

    public E unlink(Node<E> unlink) {
        E item = unlink.item;
        Node<E> prev = unlink.prev;
        Node<E> next = unlink.next;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            unlink.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            unlink.next = null;
        }

        unlink.item = null;
        size--;
        return item;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        if (first != null) {
            return first.printForward();
        }
        return "List is empty";
    }

    private static class Node<E> {
        Node<E> prev;
        E item;
        Node<E> next;

        public Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }

        public String printForward() {
            if (next != null) {
                return item + " -> " + next.printForward();
            }
            return String.valueOf(item);
        }
    }

    private static void print(DoubleLinkedList list) {
        System.out.println("size: " + list.getSize() + " | list: " + list.toString());
    }

    public static void main(String[] args) {

        DoubleLinkedList<String> list = new DoubleLinkedList<>();
        Node<String> node1 = list.addLast("1");
        Node<String> node2 = list.addLast("2");
        Node<String> node3 = list.addLast("3");

        print(list);

        list.unlink(node1);
        print(list);

        list.unlink(node2);
        print(list);

        list.unlink(node3);
        print(list);
    }
}

Output:

size: 3 | list: 1 -> 2 -> 3
size: 2 | list: 2 -> 3
size: 1 | list: 3
size: 0 | list: List is empty

References

References (Harvard CS classes - Data Structures)

Native Advertising
50 000 ad impressions - 449$
🚀
Get your tech brand or product in front of software developers.
For more information contact us:
Red dot
Dirask - friendly IT community for everyone.

❤️💻 🙂

Join