Version: Next

链表

链表的成员变量

  • size
  • first，链表的第一个节点

链表的构成单元——节点

节点的构成：

  • next：指向下一个节点
  • element：当前节点的值

size方法

// 元素 g的数目
public int size() {
return size;
}

isEmpty方法

// 是否为空
public boolean isEmpty() {
return size == 0;
}

contains方法

// 是否包含某个元素
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}

add方法

// 添加一个元素到最后面
public void add(E element) {
add(size, element);
}

toString方法

@Override
public String toString() {
StringBuilder result = new StringBuilder("MyLinkedList{" +
"size=" + size + " | ");
LinkedListNode<E> node = first;
while (node.next != null) {
result.append(node.element).append(" -> ");
node = node.next;
}
result.append(node.element).append("}");
return result.toString();
}

clear方法

将头节点设置为null，则整个链表会被垃圾回收器回收

// 清除所有元素
public void clear() {
size = 0;
first = null;
}

node(int index)方法

给定index，返回对应的节点对象

private LinkedListNode<E> node(int index) {
rangeCheck(index);
LinkedListNode<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}

get方法

// 返回index位置对应的元素
public E get(int index) {
return node(index).element;
}
  • 时间复杂度：调用了node方法，node方法为遍历链表
    • 最好情况 第一个节点就找到O(1)
    • 最差情况 最后一个节点才找到O(n)
    • 平均复杂度： 前n项和均值 = O(n)

set方法

// 设置Index位置的元素
public E set(int index, E element) {
LinkedListNode<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}

同get方法，时间复杂度为O(n)

add(int index, E element)方法

  • 找点指定index的前一个节点
  • 新节点的next域指向原index对应的节点
  • 将前一个节点指向新节点
特殊的，当index==0

在链表头插入节点，因为index等于0，一上来就执行node(index - 1)会造成下标越界，所以要做特殊处理

  • 新节点的下一个节点指向原先的first节点
  • 新节点变为现在的first节点
// 向index位置插入一个元素
public void add(int index, E element) {
if (index == 0) {
first = new LinkedListNode<>(element, first);
} else {
LinkedListNode<E> preNode = node(index - 1);
preNode.next = new LinkedListNode<>(element, preNode.next);
}
size++;
}

时间复杂度：O(n)

remove方法

  • 找到目标节点
  • 让目标节点的前一个节点指向目标节点的后一个节点
  • 目标节点被垃圾回收器自动回收
// 移除index位置的元素并返回
public E remove(int index) {
E removedElement = null;
if (index == 0) {
removedElement = first.element;
first = first.next;
} else {
LinkedListNode<E> preNode = node(index - 1);
removedElement = preNode.next.element;
preNode.next = preNode.next.next;
}
size--;
return removedElement;
}
  • 测试
public static void main(String[] args) {
MyLinkedList<Integer> list = new MyLinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(3,4);
Integer removed0 = list.remove(1);
Integer removed1 = list.remove(1);
System.out.println("removed0 = " + removed0);
System.out.println("removed1 = " + removed1);
System.out.println("list = " + list);
}
removed0 = 2
removed1 = 3
list = MyLinkedList{size=2 | 1 -> 4}

indexOf方法

// 查看元素的位置
public int indexOf(E element) {
LinkedListNode<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null)
return i;
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}

时间复杂度：O(n)

完整代码

public class MyLinkedList<E> {
private static final int ELEMENT_NOT_FOUND = -1;
private int size = 0;
private LinkedListNode<E> first;
private static class LinkedListNode<E> {
E element;
LinkedListNode<E> next;
public LinkedListNode() {
}
public LinkedListNode(E element, LinkedListNode<E> next) {
this.element = element;
this.next = next;
}
@Override
public String toString() {
return "LinkedListNode{" +
"element=" + element +
", next=" + next +
'}';
}
}
// 元素 g的数目
public int size() {
return size;
}
// 是否为空
public boolean isEmpty() {
return size == 0;
}
// 是否包含某个元素
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
// 添加一个元素到最后面
public void add(E element) {
// elements[size++] = element;
add(size, element);
}
// 返回index位置对应的元素
public E get(int index) {
return node(index).element;
}
// 设置Index位置的元素
public E set(int index, E element) {
LinkedListNode<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}
// 向index位置插入一个元素
public void add(int index, E element) {
if (index == 0) {
first = new LinkedListNode<>(element, first);
} else {
LinkedListNode<E> preNode = node(index - 1);
preNode.next = new LinkedListNode<>(element, preNode.next);
}
size++;
}
// 移除index位置的元素并返回
public E remove(int index) {
E removedElement = null;
if (index == 0) {
removedElement = first.element;
first = first.next;
} else {
LinkedListNode<E> preNode = node(index - 1);
removedElement = preNode.next.element;
preNode.next = preNode.next.next;
}
size--;
return removedElement;
}
// 查看元素的位置
public int indexOf(E element) {
LinkedListNode<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null)
return i;
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
return i;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
// 清除所有元素
public void clear() {
size = 0;
first = null;
}
private LinkedListNode<E> node(int index) {
rangeCheck(index);
LinkedListNode<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
private void outOfBoundsException(int index) {
throw new IndexOutOfBoundsException("Index:" + index + " | size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size)
outOfBoundsException(index);
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size)
outOfBoundsException(index);
}
@Override
public String toString() {
StringBuilder result = new StringBuilder("MyLinkedList{" +
"size=" + size + " | ");
LinkedListNode<E> node = first;
while (node.next != null) {
result.append(node.element).append(" -> ");
node = node.next;
}
result.append(node.element).append("}");
/* while (node != null) {
result.append(node.element).append(" -> ");
node = node.next;
}*/
return result.toString();
}
}

链表刷题注意事项

  • 一定要多画图
  • 解题技巧
    • 虚拟头节点
    • 快慢指针
    • 多指针
    • ...
  • 常用代码一定要非常熟练
    • 链表节点的插入、删除
    • 反转一个链表
    • 快慢指针求中心节点
    • 计算链表的长度