Linked List Introduction - 链表简介

Made by Mike_Zhang

母亲节快乐 🌹
Happy Mother’s Day 🌹

数据结构与算法主题：

1 Introduction to Linked List

The drawbacks of Array:

  • The capacity of an array is fixed once created;
  • The time complexity of array insertion and deletion is high for elements shifting.

Linked List:

A collection of nodes that collectively form a linear sequence, an alternative to an array-based structure.

Including Singly Linked List, Circularly Linked List, and Doubly Linked List.

2 Singly Linked List

One kind of Linked List whose each node stores a reference to an object that is next node of the list.

Singly Linked List

  • head: the first node of the linked list
    • the linked list instance must keep a reference to its head;
  • tail: the last node of the linked list
    • can be found by traversing the linked list;
    • the next reference of tail is null;
      • Alternatively, the next reference of the tail can be itself, which can also help us to find the end of the list by checking whether the next reference of a node is itself or not.
    • it is usual efficiency to store an explicit reference to the tail node for avoiding such traversal;
  • It is usual for a linked list instance to keep a count of the total number of nodes that is the size of the list, to avoid traversing the list to count the nodes.

Singly Linked List with head and tail

Java implementation of the Node:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Node<E> {
    private E data;
    private Node<E> next;

    public Node() {
        data = null;
        next = null;
    }

    public Node(E data) {
        this.data = data;
        next = null;
    }
        
    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }

    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

    public Node<E> getNext() {
        return next;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }
}

Java implementation of the Singly Linked List initialization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class SinglyLinkedList<E> {

    private Node<E> head;
    private Node<E> tail;
    private int size;
    
    public SinglyLinkedList() {
        head = new Node<>();
        tail = new Node<>();
        size = 0;
    }

    // Node class nested
    private static class Node<E> {
        // ...
    }
}

2.1 Insertion of Singly Linked List

Insert at the head

  1. Create a new node as the new head;
  2. Set the next node of the new head to point to the current head;
  3. Set the head of the list to point to the new head;

Insert at the head of Singly Linked List

Java implementation:

1
2
3
4
5
6
7
8
9
public void addAtHead(E inData) {
    Node<E> newHead = new Node<>(inData); // Create a new head, 
    newHead.setNext(head); // and set its next to point to the current head
    head = newHead; // Set the head of the list to point to the new head;
    if (size == 0) { // If the head is only node in the list
        tail = head; // The head is also the tail
    }
    size++; // Increase the size
}

Insert at the tail

  1. Create a new node as the new tail;
  2. Set the next node of the new head to point to the null;
  3. Set the tail of the list to point to the new tail;

Insert at the tail of Singly Linked List

Java implementation:

1
2
3
4
5
6
7
8
9
10
11
12
public void addAtTail(E inData) {
    Node<E> newTail = new Node<>(inData); // Create a new tail, 
    newTail.setNext(null); // and set its next to point to null
    if (size == 0) { // if the tail is only node in the list
        head = newTail; // The tail is also the head
    }
    else {
        tail.setNext(newTail); // else the new tail is the next node of current tail
    }
    tail = newTail; // Set the tail of the list to point to the new tail;
    size++; // Increase the size
}

Insert at the index

  1. If the index is 0, then call addAtHead();
  2. If the index is size, then call addAtTail();
  3. Create a new node as new node;
  4. Access the node before the index node by traversal as current node;
  5. Set the next node of the new node to point to the next node of the current node;
  6. Set the next node of the current node to point to the new node.

Insert at the index of Singly Linked List

Java implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void addAtIndex(E inData, int index) {
    if (index == 0) { // If the index is 0, then call addAtHead();
        addAtHead(inData);
    }
    else if (index == size) { // If the index is size, then call addAtTail();
        addAtTail(inData);
    }
    else {
        Node<E> newNode = new Node<>(inData); // Create a new node as new node
        Node<E> current = head;
        // Access the node before the index node by traversal
        for (int i = 0; i < index - 1; i++) {
            current = current.getNext();
        }
        // Set the next node of the new node to point to the next node of the current node
        newNode.setNext(current.getNext());
        // Set the next node of the current node to point to the new node
        current.setNext(newNode);
        size++;
    }
}

2.2 Removing of Singly Linked List

Remove the head

Just let head point to the next node of the head.

Remove the head of Singly Linked List

Remove at the index

  1. Access the node before the index node by traversal as current node;
  2. Set the next node of current node to point to the next node of next node of the current node.

Remove at the index of Singly Linked List

Java implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void deleteAtIndex(int index) {
    if (size == 0) {
        return;
    }
    if (index == 0) {
        // Just set head point to the next node of the head
        head = head.getNext();
    }
    else if (index >0 && index < size) {
        Node<E> current = head;
        // Access the node before the index node by traversal as current node
        for (int i = 0; i < index - 1; i++) {
            current = current.getNext();
        }
        // Set the next node of current node to point to the next node of next node of the current node
        current.setNext(current.getNext().getNext());
    }
    size--; // decrease the size
}

2.3 Implementation of the Singly Linked List Class

Using generics datatype in Java to define the data stored in nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
public class SinglyLinkedList<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size;

    // constructor
    public SinglyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public E getHead() {
        return head.getData();
    }

    public E getTail() {
        return tail.getData();
    }
    // get node from an index
    public Node<E> getAtIndex(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node<E> current = head;
        for (int i = 0; i < index; i++) {
            current = current.getNext();
        }
        return current;
    }

    // insert node at head
    public void addAtHead(E inData) {
        Node<E> newHead = new Node<>(inData);
        newHead.setNext(head);
        head = newHead;
        if (size == 0) {
            tail = head;
        }
        size++;
    }

    // insert node at tail
    public void addAtTail(E inData) {
        Node<E> newTail = new Node<>(inData);
        newTail.setNext(null);
        if (size == 0) {
            head = newTail;
        }
        else {
            tail.setNext(newTail);
        }
        tail = newTail;
        size++;
    }

    // insert node at an index
    public void addAtIndex(E inData, int index) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            addAtHead(inData);
        }
        else if (index == size) {
            addAtTail(inData);
        }
        else {
            Node<E> newNode = new Node<>(inData);
            Node<E> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.getNext();
            }
            newNode.setNext(current.getNext());
            current.setNext(newNode);
            size++;
        }
    }
    // remove and return a node at head
    public E deleteAtHead() {
        if (size == 0) {
            return null;
        }
        E data = head.getData();
        head = head.getNext();
        size--;
        if (size == 0) {
            tail = head;
        }
        return data;
    }

    // remove and return a node at an index
    public E deleteAtIndex(int index) {
        E data = null;
        if (size == 0) {
            return null;
        }
        if (index == 0) {
            return deleteAtHead();
        }
        else if (index >0 && index < size) {
            Node<E> current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.getNext();
            }
            data = current.getNext().getData();
            current.setNext(current.getNext().getNext());
        }
        size--;
        return data;
    }

    // Node class
    private static class Node<E> {
        private E data;
        private Node<E> next;

        public Node() {
            data = null;
            next = null;
        }

        public Node(E data) {
            this.data = data;
            next = null;
        }

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

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    }
}

2.4 Reverse Singly Linked List

To reverse a Singly Linked List.

Reverse Singly Linked List

The main idea is move the node after the old head(as the new head) to the front of the list(as the head) one by one till the head become the tail of the list.

Reverse Singly Linked List

Java implementation:

1
2
3
4
5
6
7
8
9
public void reverse() {
    Node<E> oldHead = this.head; // initial the oldHead to the head
    while (oldHead != null && oldHead.next != null) { // loop till lodHead become the tail
        Node<E> newHead = oldHead.next; // Set the newHead as the next of oldHead
        oldHead.next = newHead.next; // Set next node of the old one to new one's next
        newHead.next = this.head; // Main idea: Move the newHead to the front of the list, to become the current head
        this.head = newHead; // Let head point to the newHead
    }
}

3 Circularly Linked List

Circularly Linked List is a special case of Singly Linked List, which the next node of the tail points back to the head of the list, rather than null;

Circularly Linked List

  • NO maintain of the head reference;
  • Once we have the reference to the tail, tail.getNext() refers to the head of the list;
    • It saves a bit of memory storage;
    • And simplify the code and make it more efficient, since it no need to maintain an additional head reference;

3.1 Rotate a Circularly Linked List

Just let the current tail node point to its next node:

Rotate a Circularly Linked List

Java implementation:

1
2
3
4
5
public void rotate() {
    if (tail != null) {
        tail = tail.next;
    }
}

3.2 Insert and Remove Node from a Circularly Linked List

Similar to Insertion of Singly Linked List and Removing of Singly Linked List.

Insert and Remove Node from a Circularly Linked List

Some keys:

  • Insert at the head of the list: just insert the new node after the tail node;
  • Insert at the tail of the list: first call method to insert the new node at the head, then set the tail reference point to the new node.

3.3 Implementation of the Circularly Linked List Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
public class CircularlyLinkedList<E> {
    private Node<E> tail;
    private int size;

    public CircularlyLinkedList() {
        tail = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public Node<E> getTail() {
        return tail;
    }

    public Node<E> getHead() {
        if (tail == null) {
            return null;
        }
        return tail.next;
    }

    public E getHeadData() {
        return getHead().data;
    }

    public String toString() {
        if (isEmpty()) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Node<E> current = getHead();
        sb.append(current.getData() + " ");
        current = current.getNext();
        while (current != getHead()) {
            sb.append(current.getData() + " ");
            current = current.getNext();
        }
        return sb.toString();
    }

    public void rotate() {
        if (tail != null) {
            tail = tail.next;
        }
    }

    public void addAtHead (E e) {
        Node<E> newNode = new Node<E>(e);
        if (size == 0) {
            tail = newNode;
            tail.setNext(tail);
        }
        else {
            newNode.next = tail.getNext();
            tail.setNext(newNode);
        }
        size++;
    }

    public void addAtTail (E e) {
        addAtHead(e);
        tail = tail.next;
    }

    public void addAtIndex (int index, E e) {
        if (index == 0) {
            addAtHead(e);
        }
        else if (index == size) {
            addAtTail(e);
        }
        else {
            Node<E> current = getHead();
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            Node<E> newNode = new Node<E>(e);
            newNode.next = current.next;
            current.next = newNode;
            size++;
        }
    }

    public void deleteAtIndex (int index) {
        if (isEmpty()) {
            return;
        }
        if (index == 0) {
            if (size == 1) {
                tail = null;
            }
            else {
                tail.setNext(tail.next.next);
            }
        }
        else if (index>0 && index<size) {
            Node<E> current = getHead();
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            current.next = current.next.next;
            size--;
        }
    }

    public E deleteAtHead(){
        E out = null;
        if (size == 1) {
            out = tail.data;
            tail = null;
        }
        else {
            out = tail.next.data;
            tail.setNext(tail.next.next);
        }
        size--;
        return out;
    }

    private static class Node<E> {
        private E data;
        private Node<E> next;

        public Node() {
            data = null;
            next = null;
        }

        public Node(E data) {
            this.data = data;
            next = null;
        }

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

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    }
}

4 Doubly Linked List

Problem:

In the Singly Linked List, it is not efficient to insert and delete a arbitrary node except the head node, because we cannot determine the node that immediately precedes the arbitrary node, since we only know the next node of it.

Solution:

Based on the Singly Linked List, we add an additional reference in each node to point to the node before it, which is the Doubly Linked List.

Using next to point to the next node.
Using prev to point to the previous node.

Example of Doubly Linked List

Java implementation of the Node in Doubly Linked List:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Node<E> {
        private E data;
        private Node<E> next;
        private Node<E> prev;

        public Node() {
            data = null;
            next = null;
            prev = null;
        }

        public Node(E data) {
            this.data = data;
            next = null;
            prev = null;
        }

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

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node<E> getPrev() {
            return prev;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    }

4.1 Header and Trailer Sentinels

It is helpful to add additional nodes at ends of the list:

  • A header node ar the beginning of the list, and a trailer node the end of the list;
  • They called sentinels or guards, they do not store elements of thr primary list;
  • For an empty list, the next field of header points to trailer, and the prev field of trailer points to header, the rest will be set as null;
  • For n nonempty, the next field of header points to the first element in the sequence, prev field of trailer points to last element of the sequence.

Header and Trailer Sentinels

Advantage of Using Sentinels:

  • The slight extra memory for the sentinels greatly simplifies the logic of our operations;
  • The header and trailer node will never be changed;
  • Treat all insertion and deletion in unified manners, since every element is guaranteed to be store in node with nodes as neighbors on both sides.

4.2 Inserting in Doubly Linked List

Insert x between a and b node:

  1. Create a new node as x;
  2. Set the next field of x to point to node b, set the prev field of x to point to node a (step b);
  3. Set the next field of a to point to node x, set the prev field of b to point to node x (step c);

Inserting in Doubly Linked List

Java implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
public void addBetween(E data, Node<E> prev, Node<E> next) {
    Node<E> newNode = new Node<>(data);
    
    // Step 2
    newNode.setPrev(prev);
    newNode.setNext(next);

    // Step 3
    prev.setNext(newNode);
    next.setPrev(newNode);

    size++;
}

4.3 Deleting in Doubly Linked List

Simply idea:

The two neighbors of the node to be deleted are linked directly to each other, thereby bypassing the original node.

  1. Set the next of the prev node of deleted node to point to the deleted node’s next node;
  2. Set the prev of the next node of deleted node to point to the deleted node’s prev node;
  • In the following example, the neighbors of the node 3, which are node 2 and 4, are linked directly to each other, so node 3 is skipped when traversing the list, seems that the node 3 is deleted.

Deleting in Doubly Linked List

Java implementation:

1
2
3
4
5
6
7
8
9
public Node<E> delete(Node<E> node) {
    if (node == null) {
        return null;
    }
    node.getPrev().setNext(node.getNext()); // Step 1
    node.getNext().setPrev(node.getPrev()); // Step 2
    size--;
    return node;
}

4.4 Implementation of the Doubly Linked List Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
public class DoublyLinkedList<E> {

    private Node<E> header;
    private Node<E> trailer;
    private int size;

    // constructor
    public DoublyLinkedList() {
        header = new Node<>();
        trailer = new Node<>();
        header.setNext(trailer);
        trailer.setPrev(header);
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public Node<E> getHead() {
        return header.getNext();
    }

    public Node<E> getTail() {
        return trailer.getPrev();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<E> current = this.getHead();
        while (current != trailer) {
            sb.append(current.getData() + " ");
            current = current.getNext();
        }
        return sb.toString();
    }

    // Get a node at an index
    public Node<E> getAtIndex(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        Node<E> current = this.getHead();
        for (int i = 0; i < index; i++) {
            current = current.getNext();
        }
        return current;
    }

    // Add a node between two nodes
    public void addBetween(E data, Node<E> prev, Node<E> next) {
        Node<E> newNode = new Node<>(data);
        newNode.setPrev(prev);
        newNode.setNext(next);
        prev.setNext(newNode);
        next.setPrev(newNode);
        size++;
    }

    // Add a node at the head of list
    public void addAtHead(E data) {
        addBetween(data, header, header.getNext());
    }

    // Add a node at the tail of list
    public void addAtTail(E data) {
        addBetween(data, trailer.getPrev(), trailer);
    }

    // Add a node at an index of list
    public void addAtIndex(E data, int index) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            addAtHead(data);
        }
        else if (index == size) {
            addAtTail(data);
        }
        else {
            Node<E> prev = getAtIndex(index - 1);
            addBetween(data, prev, prev.getNext());
        }
    }

    // Remove a special node
    public Node<E> delete(Node<E> node) {
        if (node == null) {
            return null;
        }
        node.getPrev().setNext(node.getNext());
        node.getNext().setPrev(node.getPrev());
        size--;
        return node;
    }

    // Remove the head node
    public Node<E> deleteAtHead() {
        if (isEmpty()) {
            return null;
        }
        return delete(header.getNext());
    }

    // Remove the tail node 
    public Node<E> deleteAtTail() {
        if (isEmpty()) {
            return null;
        }
        return delete(trailer.getPrev());
    }

    // Remove a node at an index
    public Node<E> deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        if (index == 0) {
            return deleteAtHead();
        }
        else if (index == size - 1) {
            return deleteAtTail();
        }
        else {
            Node<E> prev = getAtIndex(index - 1);
            return delete(prev.getNext());
        }
    }

    // Node class
    private static class Node<E> {
        private E data;
        private Node<E> next;
        private Node<E> prev;

        public Node() {
            data = null;
            next = null;
            prev = null;
        }

        public Node(E data) {
            this.data = data;
            next = null;
            prev = null;
        }

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

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node<E> getPrev() {
            return prev;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    }
}

Linked List Problem Set

Refer to Linked List Problems

References

Goodrich, M., Tamassia, R., & O’reilly, A. (2014). Data Structures and Algorithms in Java, 6th Edition. John Wiley & Sons.
Linked List - Explore - LeetCode

写在最后

Linked List 相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Data Structure and Algorithm > Data Structure > Linked List
#Java #数据结构 #Linked List
Linked List Introduction - 链表简介
https://ultrafish.io/post/linked-list-introduction/
Author
Mike_Zhang
Posted on
May 8, 2022
Licensed under