+关注继续查看

# 一、概述

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

# 二、单向链表

public class SinglyLinkedList {

private static class Node { // 节点类
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
}

Node 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构

public class SinglyLinkedList {
// ...
}
}

while 遍历

public class SinglyLinkedList {
// ...
public void loop() {
while (curr != null) {
// 做一些事
curr = curr.next;
}
}
}

for 遍历

public class SinglyLinkedList {
// ...
public void loop() {
for (Node curr = this.head; curr != null; curr = curr.next) {
// 做一些事
}
}
}

Consumer 的规则是一个参数，无返回值，因此像 System.out::println 方法等都是 Consumer

public class SinglyLinkedList implements Iterable<Integer> {
// ...
private class NodeIterator implements Iterator<Integer> {

public boolean hasNext() {
return curr != null;
}
public Integer next() {
int value = curr.value;
curr = curr.next;
return value;
}
}

public Iterator<Integer> iterator() {
return new NodeIterator();
}
}

hasNext 用来判断是否还有必要调用 next

next 做两件事

public class SinglyLinkedList implements Iterable<Integer> {
// ...
public void loop() {
}
private void recursion(Node curr) {
if (curr == null) {
return;
}
// 前面做些事
recursion(curr.next);
// 后面做些事
}
}

public class SinglyLinkedList {
// ...
private Node findLast() {
return null;
}
Node curr;
for (curr = this.head; curr.next != null; ) {
curr = curr.next;
}
return curr;
}

Node last = findLast();
if (last == null) {
return;
}
last.next = new Node(value, null);
}
}

public class SinglyLinkedList {
// ...
public void addLast(int first, int... rest) {

Node sublist = new Node(first, null);
Node curr = sublist;
for (int value : rest) {
curr.next = new Node(value, null);
curr = curr.next;
}

Node last = findLast();
if (last == null) {
return;
}
last.next = sublist;
}
}

public class SinglyLinkedList {
// ...
private Node findNode(int index) {
int i = 0;
for (Node curr = this.head; curr != null; curr = curr.next, i++) {
if (index == i) {
return curr;
}
}
return null;
}

private IllegalArgumentException illegalIndex(int index) {
return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
}

public int get(int index) {
Node node = findNode(index);
if (node != null) {
return node.value;
}
throw illegalIndex(index);
}
}

public class SinglyLinkedList {
// ...
public void insert(int index, int value) {
if (index == 0) {
return;
}
Node prev = findNode(index - 1); // 找到上一个节点
if (prev == null) { // 找不到
throw illegalIndex(index);
}
prev.next = new Node(value, prev.next);
}
}

public class SinglyLinkedList {
// ...
public void remove(int index) {
if (index == 0) {
return;
} else {
throw illegalIndex(index);
}
}
Node prev = findNode(index - 1);
Node curr;
if (prev != null && (curr = prev.next) != null) {
prev.next = curr.next;
} else {
throw illegalIndex(index);
}
}
}

|
15天前
|
C++
LeetCode 138.复制带随机指针的链表
LeetCode 138.复制带随机指针的链表
12 0
|
15天前
|
C++ 索引
LeetCode 142.环形链表II
LeetCode 142.环形链表II
18 0
|
15天前
|
C++ 索引
LeetCode 141.环形链表
LeetCode 141.环形链表
12 0
|
15天前
|
C++
LeetCode 160.相交链表
LeetCode 160.相交链表
19 0
|
23天前
【 LeetCode题解 】203. 移除链表元素
【 LeetCode题解 】203. 移除链表元素 当val在链表中间时，遇到val就删除链表中和val相同的节点，并链接val后面的节点。 当val在链表开头时，或者连续的时候，我们将链表其实的head(头)向后移动，直到找到不是val的节点,作为开始的头。
24 0
|
4月前
|

Algorithms_基础数据结构(04)_线性表之链表_单向循环链表&约瑟夫环问题
Algorithms_基础数据结构(04)_线性表之链表_单向循环链表&约瑟夫环问题
47 0
|
4月前
|

Algorithms_基础数据结构(03)_线性表之链表_双向链表
Algorithms_基础数据结构(03)_线性表之链表_双向链表
44 0
|
4月前
|

【算法之旅】基础数据结构之链表（二）
【算法之旅】基础数据结构之链表（二）
418 0
|
7月前
|

61 0
|

96 0