链表代码实现
Key Points
Next, I will provide a simple MyLinkedList implementation using both doubly linked lists and singly linked lists, including basic functions such as adding, deleting, searching, and modifying elements. Here are a few key points to keep in mind while reviewing the code.
Key Point 1: Hold References to Both Head and Tail Nodes
When solving problems on LeetCode, we are usually given the head pointer of a singly linked list. However, in actual development, doubly linked lists are more commonly used, typically holding references to both the head and tail nodes.
In software development, adding elements to the tail of a list is a very frequent operation. By holding a reference to the tail node in a doubly linked list, this operation can be performed in O(1) time complexity.
For singly linked lists, holding a reference to the tail node also provides optimization. For example, if you want to add an element to the tail of a singly linked list and you don't have a reference to the tail node, you need to traverse the entire list to find it, which has a time complexity of O(n). However, if you have a reference to the tail node, the operation can be done in O(1) time complexity.
Attentive readers might point out that if you delete the tail node of a singly linked list, the previous tail node reference becomes invalid, requiring a traversal to find the new tail node.
That's correct, but if you think about it, when deleting the tail node of a singly linked list, you also need to traverse to the second-to-last node (the predecessor of the tail node) to delete the tail node through pointer manipulation. At that point, you can update the tail node reference as well.
Key Point Two: Dummy Head and Tail Nodes
In the previous article Linked List Basics, I mentioned the "dummy head and tail node" technique. The principle is simple: when creating a doubly linked list, you create a dummy head node and a dummy tail node. These nodes exist regardless of whether the doubly linked list is empty or not. This approach prevents null pointer issues and avoids handling many edge cases.
For example, assuming the dummy head and tail nodes are dummyHead and dummyTail, an empty doubly linked list looks like this:
dummyHead <-> dummyTailIf you add elements 1, 2, 3, the linked list looks like this:
dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTailPreviously, you had to consider different scenarios for inserting elements at the head, tail, and middle of the list. Now, with the dummy head and tail nodes, you only need to handle the middle insertion case, simplifying the code significantly.
Of course, the dummy head node uses a bit more memory, but this small cost is worthwhile given the problems it solves.
For a singly linked list, a dummy head node simplifies the implementation to some extent, but a dummy tail node is not as useful.
Key Point Three: Memory Leaks?
In the earlier article Dynamic Array Implementation, I mentioned the issue of memory leaks when deleting elements. So, does deleting elements in a linked list also cause memory leaks?
Consider the following code. Do you think it has any issues:
// Assume the head node of the singly linked list is head = 1 -> 2 -> 3 -> 4 -> 5
// Delete the head node of the singly linked list
head = head.next;
// At this point, head = 2 -> 3 -> 4 -> 5Careful readers might think that writing code this way could cause a memory leak because the next pointer of the original head node 1 is not disconnected and still points to node 2.
However, this approach is actually fine because Java's garbage collection mechanism determines whether an object is referenced by others, rather than whether the object itself references others.
The next pointer of node 1 indeed still points to node 2, but since no other pointers reference node 1, it will eventually be collected and freed by the garbage collector. Therefore, this scenario is different from deleting elements in an array. You can think about it more carefully.
Nonetheless, when deleting a node, it's a good practice to set the pointers of the deleted node to null, even if it's not strictly necessary. This habit doesn't come at any cost and can prevent potential issues. So, in the implementation below, I will set the pointers of the deleted node to null regardless of necessity.
How to Verify Your Implementation?
You can use LeetCode problem 707 "Design Linked List" to verify whether your implementation is correct.
Doubly Linked List Code Implementation
import java.util.NoSuchElementException;
public class MyLinkedList<E> {
// virtual head and tail nodes
final private Node<E> head, tail;
private int size;
// doubly linked list node
private static class Node<E> {
E val;
Node<E> next;
Node<E> prev;
Node(E val) {
this.val = val;
}
}
// constructor initializes virtual head and tail nodes
public MyLinkedList() {
this.head = new Node<>(null);
this.tail = new Node<>(null);
head.next = tail;
tail.prev = head;
this.size = 0;
}
// ***** Add *****
public void addLast(E e) {
Node<E> x = new Node<>(e);
Node<E> temp = tail.prev;
// temp <-> tail
temp.next = x;
x.prev = temp;
x.next = tail;
tail.prev = x;
// temp <-> x <-> tail
size++;
}
public void addFirst(E e) {
Node<E> x = new Node<>(e);
Node<E> temp = head.next;
// head <-> temp
temp.prev = x;
x.next = temp;
head.next = x;
x.prev = head;
// head <-> x <-> temp
size++;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) {
addLast(element);
return;
}
// find the Node corresponding to index
Node<E> p = getNode(index);
Node<E> temp = p.prev;
// temp <-> p
// new Node to be inserted
Node<E> x = new Node<>(element);
p.prev = x;
temp.next = x;
x.prev = temp;
x.next = p;
// temp <-> x <-> p
size++;
}
// ***** Remove *****
public E removeFirst() {
if (size < 1) {
throw new NoSuchElementException();
}
// the existence of virtual nodes prevents us from having to consider null pointers
Node<E> x = head.next;
Node<E> temp = x.next;
// head <-> x <-> temp
head.next = temp;
temp.prev = head;
x.prev = null;
x.next = null;
// head <-> temp
size--;
return x.val;
}
public E removeLast() {
if (size < 1) {
throw new NoSuchElementException();
}
Node<E> x = tail.prev;
Node<E> temp = tail.prev.prev;
// temp <-> x <-> tail
tail.prev = temp;
temp.next = tail;
x.prev = null;
x.next = null;
// temp <-> tail
size--;
return x.val;
}
public E remove(int index) {
checkElementIndex(index);
// find the Node corresponding to index
Node<E> x = getNode(index);
Node<E> prev = x.prev;
Node<E> next = x.next;
// prev <-> x <-> next
prev.next = next;
next.prev = prev;
x.prev = x.next = null;
// prev <-> next
size--;
return x.val;
}
// ***** Get *****
public E get(int index) {
checkElementIndex(index);
// find the Node corresponding to index
Node<E> p = getNode(index);
return p.val;
}
public E getFirst() {
if (size < 1) {
throw new NoSuchElementException();
}
return head.next.val;
}
public E getLast() {
if (size < 1) {
throw new NoSuchElementException();
}
return tail.prev.val;
}
// ***** Set *****
public E set(int index, E val) {
checkElementIndex(index);
// find the Node corresponding to index
Node<E> p = getNode(index);
E oldVal = p.val;
p.val = val;
return oldVal;
}
// ***** Other utility functions *****
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private Node<E> getNode(int index) {
checkElementIndex(index);
Node<E> p = head.next;
// TODO: Can be optimized by deciding whether to traverse from head or tail based on index
for (int i = 0; i < index; i++) {
p = p.next;
}
return p;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
// Check if the index position can contain an element
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// Check if the index position can add an element
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private void display() {
System.out.println("size = " + size);
for (Node<E> p = head.next; p != tail; p = p.next) {
System.out.print(p.val + " -> ");
}
System.out.println("null");
System.out.println();
}
}Singly Linked List Code Implementation
import java.util.NoSuchElementException;
public class MyLinkedList2<E> {
private static class Node<E> {
E val;
Node<E> next;
Node(E val) {
this.val = val;
this.next = null;
}
}
private Node<E> head;
// actual reference to the tail node
private Node<E> tail;
private int size;
public MyLinkedList2() {
this.head = new Node<>(null);
this.tail = head;
this.size = 0;
}
public void addFirst(E e) {
Node<E> newNode = new Node<>(e);
newNode.next = head.next;
head.next = newNode;
if (size == 0) {
tail = newNode;
}
size++;
}
public void addLast(E e) {
Node<E> newNode = new Node<>(e);
tail.next = newNode;
tail = newNode;
size++;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) {
addLast(element);
return;
}
Node<E> prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node<E> newNode = new Node<>(element);
newNode.next = prev.next;
prev.next = newNode;
size++;
}
public E removeFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Node<E> first = head.next;
head.next = first.next;
if (size == 1) {
tail = head;
}
size--;
return first.val;
}
public E removeLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Node<E> prev = head;
while (prev.next != tail) {
prev = prev.next;
}
E val = tail.val;
prev.next = null;
tail = prev;
size--;
return val;
}
public E remove(int index) {
checkElementIndex(index);
Node<E> prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node<E> nodeToRemove = prev.next;
prev.next = nodeToRemove.next;
// deleting the last element
if (index == size - 1) {
tail = prev;
}
size--;
return nodeToRemove.val;
}
// ***** Retrieve *****
public E getFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return head.next.val;
}
public E getLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return getNode(size - 1).val;
}
public E get(int index) {
checkElementIndex(index);
Node<E> p = getNode(index);
return p.val;
}
// ***** Update *****
public E set(int index, E element) {
checkElementIndex(index);
Node<E> p = getNode(index);
E oldVal = p.val;
p.val = element;
return oldVal;
}
// ***** Other Utility Functions *****
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
// Check if the index position can have an element
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// Check if the index position can add an element
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// Return the Node corresponding to the index
// Note: Please ensure that the passed index is valid
private Node<E> getNode(int index) {
Node<E> p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p;
}
}