Codecademy Logo

Doubly Linked Lists

Related learning

  • Skill path

    Pass the Technical Interview with Java

    Learn about the computer science concepts of data structures and algorithms and build implementations of each from scratch in modern Java.
    • Includes 8 Courses
    • With Certificate
    • Intermediate.
      19 hours

Adding to the Tail

A Java DoublyLinkedList class can implement an .addToTail() instance method for adding new data to the tail of the list. .addToTail() takes a single data argument. It uses data to create a new Node which it adds to the tail of the list.

  public void addToTail(String data) {
    Node newTail = new Node(data);
    Node currentTail = this.tail;


    if (currentTail != null) {
      currentTail.setNextNode(newTail);
      newTail.setPreviousNode(currentTail);
    }
    this.tail = newTail;


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

Adding to the Head

A Java DoublyLinkedList class can implement an .addToHead() instance method for adding new data to the head of the list. .addToHead() takes a single data argument. It uses data to create a new Node which it adds to the head of the list.

  public void addToHead(String data) {
    Node newHead = new Node(data);
    Node currentHead = this.head;


    if (currentHead != null) {
      currentHead.setPreviousNode(newHead);
      newHead.setNextNode(currentHead);
    }
    this.head = newHead;


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

Removing the Tail

A Java DoublyLinkedList class can implement a .removeTail() instance method for removing the tail of the list. .removeTail() takes no arguments. It removes and returns the tail of the list’s data, and sets the tail’s previous node as the new tail.

  public String removeTail() {
    Node removedTail = this.tail;


    if (removedTail == null) {
      return null;
    }
    this.tail = removedTail.getPreviousNode();


    if (this.tail != null) {
      this.tail.setNextNode(null);
    }
    if (removedTail == this.head) {
      this.removeHead();
    }
    return removedTail.data;
  }

Removing the Head

A Java DoublyLinkedList class can implement a .removeHead() instance method for removing the head of the list. .removeHead() takes no arguments. It removes and returns the head of the list’s data, and sets the head’s next node as the new head.

  public String removeHead() {
    Node removedHead = this.head;


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


    if (this.head != null) {
      this.head.setPreviousNode(null);
    }
    if (removedHead == this.tail) {
      this.removeTail();
    }
    return removedHead.data;
  }

Constructor and Instance Variables

A Java DoublyLinkedList class has two Node instance variables:

  • a public head
  • a public tail

The constructor takes no parameters and sets both instance variables to null.

public Node head;
public Node tail;


public DoublyLinkedList() {
  this.head = null;
  this.tail = null;
}

Doubly Linked List Overview

A DoublyLinkedList class in Java has the following attributes:

  • public head and tail instance Node variables
  • a constructor that sets the head and tail nodes to null
  • an .addToHead() method to add new nodes to the head
  • an .addToTail() method to add new nodes to the tail
  • a .removeHead() method to remove the head node
  • a .removeTail() method to remove the tail node
  • a .removeByData() method to remove a node that matches the data passed in
public class DoublyLinkedList {
  
  public Node head;
  public Node tail;


  public DoublyLinkedList() {
    this.head = null;
    this.tail = null;
  }


  public void addToHead(String data) {
    Node newHead = new Node(data);
    Node currentHead = this.head;


    if (currentHead != null) {
      currentHead.setPreviousNode(newHead);
      newHead.setNextNode(currentHead);
    }
    this.head = newHead;


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


  public void addToTail(String data) {
    Node newTail = new Node(data);
    Node currentTail = this.tail;


    if (currentTail != null) {
      currentTail.setNextNode(newTail);
      newTail.setPreviousNode(currentTail);
    }
    this.tail = newTail;


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


  public String removeHead() {
    Node removedHead = this.head;


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


    if (this.head != null) {
      this.head.setPreviousNode(null);
    }
    if (removedHead == this.tail) {
      this.removeTail();
    }
    return removedHead.data;
  }


  public String removeTail() {
    Node removedTail = this.tail;


    if (removedTail == null) {
      return null;
    }
    this.tail = removedTail.getPreviousNode();


    if (this.tail != null) {
      this.tail.setNextNode(null);
    }
    if (removedTail == this.head) {
      this.removeHead();
    }
    return removedTail.data;
  }


  public Node removeByData(String data) {
    Node nodeToRemove = null;
    Node currentNode = this.head;


    while (currentNode != null) {
      if (currentNode.data == data) {
        nodeToRemove = currentNode;
        break;
      }
      currentNode = currentNode.getNextNode();
    }


    if (nodeToRemove == null) {
      return null;
    }
    if (nodeToRemove == this.head) {
      this.removeHead();
    } else if (nodeToRemove == this.tail) {
      this.removeTail();
    } else {
      Node nextNode = nodeToRemove.getNextNode();
      Node previousNode = nodeToRemove.getPreviousNode();
      nextNode.setPreviousNode(previousNode);
      previousNode.setNextNode(nextNode);
    }
    return nodeToRemove;
  }


}

Removing by Data

A Java DoublyLinkedList class can implement a .removeByData() instance method that takes data as an argument and returns the node that matches data, or null if no match exists. If the node exists, .removeByData() removes it from the list and correctly resets the pointers of its surrounding nodes.

public Node removeByData(String data) {
    Node nodeToRemove = null;
    Node currentNode = this.head;


    while (currentNode != null) {
      if (currentNode.data == data) {
        nodeToRemove = currentNode;
        break;
      }
      currentNode = currentNode.getNextNode();
    }


    if (nodeToRemove == null) {
      return null;
    }
    if (nodeToRemove == this.head) {
      this.removeHead();
    } else if (nodeToRemove == this.tail) {
      this.removeTail();
    } else {
      Node nextNode = nodeToRemove.getNextNode();
      Node previousNode = nodeToRemove.getPreviousNode();
      nextNode.setPreviousNode(previousNode);
      previousNode.setNextNode(nextNode);
    }
    return nodeToRemove;
  }

Updated Node Class

Doubly linked lists in Java utilize an updated Node class that has a pointer to the previous node. This comes with additional setter and getter methods for accessing the previous node.

public class Node {


  public String data;
  private Node next;
  private Node previous;


  public Node(String data) {
    this.data = data;
    this.next = null;
  }
  
  public void setNextNode(Node node) {
    this.next = node;
  }


  public void setPreviousNode(Node node) {
    this.previous = node;
  }


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


  public Node getPreviousNode() {
    return this.previous;
  }


}

Learn more on Codecademy

  • Skill path

    Pass the Technical Interview with Java

    Learn about the computer science concepts of data structures and algorithms and build implementations of each from scratch in modern Java.
    • Includes 8 Courses
    • With Certificate
    • Intermediate.
      19 hours
Previous
Next