Linked lists

 1class Node {
 2  int data;
 3  Node next;
 4  Node(int value) {
 5    data = value;
 6    next = null;
 7  }
 8}
 9
10public class Main {
11  static void printList(Node start) {
12    Node current = start;
13    while (current != null) {
14      System.out.print(current.data + " -> ");
15      current = current.next;
16    }
17    System.out.println("null");
18  }
19
20  public static void main(String[] args) {
21    Node head = new Node(10);
22    Node twenty = new Node(20);
23    head.next = twenty;
24    twenty.next = new Node(30);
25    printList(head);
26
27    // 1. insert 5 at the beginning
28    Node newNode = new Node(5);
29    newNode.next = head;
30    head = newNode;
31    printList(head);
32
33    // 2. insert 25 after node 20
34    Node current = twenty;
35    newNode = new Node(25);
36    newNode.next = current.next;
37    current.next = newNode;
38    printList(head);
39
40    // 3. delete the node after 20 (bypass it)
41    Node previous = twenty;
42    previous.next = previous.next.next;
43    printList(head);
44
45    // 4. delete the first node
46    head = head.next;
47    printList(head);
48  }
49}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

10 -> 20 -> 30 -> null
5 -> 10 -> 20 -> 30 -> null
5 -> 10 -> 20 -> 25 -> 30 -> null
5 -> 10 -> 20 -> 30 -> null
10 -> 20 -> 30 -> null

The four operations are the same as in a singly list. Two things change: how many links you update, and how a loop knows when to stop.

Doubly linked: insert after a node. Each node has one new field, prev, the node before it. In a singly list, inserting after a node changed 2 links (the safe order ). In a doubly list it changes 4: two for the new node, and one for each neighbor.

Here are the four changes, in order:

The safe order is the same idea as before: give the new node its links first (steps 1 and 2), then point the neighbors at it (steps 3 and 4). If you do step 4 first, current.next is already 25, so step 2 makes 25 point at itself, and 30 is lost.

 1public class DoublyDemo {
 2  // insert newNode right after current: 4 links change
 3  static void insertAfter(DNode current, DNode newNode) {
 4    newNode.prev = current;          // step 1: 25 looks back at 20
 5    newNode.next = current.next;     // step 2: 25 looks ahead at 30
 6    if (current.next != null) {      // (no next node at the end)
 7      current.next.prev = newNode;   // step 3: 30 looks back at 25
 8    }
 9    current.next = newNode;          // step 4: 20 looks ahead at 25
10  }
11
12  public static void main(String[] args) {
13    DNode head = new DNode(20);
14    DNode tail = new DNode(30);
15    head.next = tail;
16    tail.prev = head;
17
18    insertAfter(head, new DNode(25));
19
20    DNode current = head;            // forward, using next
21    while (current != null) {
22      System.out.print(current.data + " ");
23      current = current.next;
24    }
25    System.out.println();            // 20 25 30
26
27    current = tail;                  // backward, using prev
28    while (current != null) {
29      System.out.print(current.data + " ");
30      current = current.prev;
31    }
32    System.out.println();            // 30 25 20
33  }
34}
35
36class DNode {
37  int data;
38  DNode prev;   // NEW: the node before this one
39  DNode next;
40
41  DNode(int value) {
42    data = value;
43    prev = null;
44    next = null;
45  }
46}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class DoublyDemo to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

The if handles inserting after the last node: there is no next node, so there is no step 3. Deleting is shorter. To remove a node x that is not first or last, you need only x.prev.next = x.next; and x.next.prev = x.prev;. You do not have to search for the node before it, because x.prev already points to it.

Circular: walk the list once. In a circular list, current never becomes null, so the usual while (current != null) loop would print 10 20 30 10 20 30 … forever. Instead, print the first node, then stop when you are back at the head:

 1public class CircularDemo {
 2  public static void main(String[] args) {
 3    Node head = new Node(10);
 4    head.next = new Node(20);
 5    head.next.next = new Node(30);
 6    head.next.next.next = head;      // 30 points back to 10
 7
 8    System.out.print(head.data + " ");   // print the first node
 9    Node current = head.next;
10    while (current != head) {        // stop when back at the start
11      System.out.print(current.data + " ");
12      current = current.next;
13    }
14    System.out.println();            // 10 20 30
15  }
16}
17
18class Node {
19  int data;
20  Node next;
21
22  Node(int value) {
23    data = value;
24    next = null;
25  }
26}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class CircularDemo to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

This loop assumes the list has at least one node. If head can be null, check that first.

How do the three kinds compare in speed? Once you have the node, inserting or deleting takes a few steps in all three kinds, however long the list is. Doubly does about twice the link work and stores one more reference per node. In return, it can go backward, and it can delete a node without searching for the one before it.