重要说明
图片与实际代码无关，这里引用的图片有很大一部分是把头结点当做链表的第一个元素，我写的示例代码不将头结点视为第一个元素
链表的概念
简单来说就是说从头结点出发，每一个结点都有一个指向后继结点的 next 指针，表中最后一个元素的 next 指向 null
链表的构造结构
这里我们使用 Java 来创建单链表的基本结构，这里是 Leetcode 常用的构建方法
public class ListNode {
public int val;
public ListNode next;
ListNode(int x) {
val = x;
next = null;
}
ListNode node = new ListNode(1);
}
|
对于简化的构造方法，你应该使用以下的代码对结点进行修改赋值
node.next = new_node;
node.val = number;
|
为了练习 Java 的面向对象特性，这里我不用简化的构造方法。
public class ListNode {
private int data;
private ListNode next;
public ListNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
}
|
而这种方式的修改赋值就是调用 get 和 set 办法
node.setNext(new_node);
node.setNext(new_node.getNext());
node.setData(number);
node.getData();
|
链表的增删改查 - 增
任何数据结构都避免不了的最基础的操作，首先来看最基础的构建链表。
对于单链表来说，构建链表有两种方式，一种是头插法，一种是尾插法。
头插法
头插法简单说来就是逆序插入，每次插入将新节点的 next 指向头结点的 next，然后将头结点的 next 指向新结点。
public ListNode headInsert(ListNode head, ListNode node) {
node.setNext(head.getNext());
head.setNext(node);
return head;
}
|
尾插法
尾插法简单来说就是顺序插入，每次插入都将此时的“头结点”的 next 改成新结点 node，然后将新结点 node 座位链表尾部，next 改为 null。和头插法不一样的是，尾插法每次返回的结点并不是头结点，所以在构建链表的时候记得保存头结点的信息。
public ListNode tailInsert(ListNode head, ListNode node) {
head.setNext(node);
node.setNext(null);
return node;
}
|
构建链表
这段代码展示了在测试类中初始化链表的全过程，这里我用 L 结点保存尾插时头结点的信息，后续会用到。
public static void main(String[] args) {
ListNodeTest test = new ListNodeTest();
ListNode head = new ListNode(-1);
head.setNext(null);
ListNode L = head;
test.initList(head, 5);
}
public ListNode initList(ListNode head, int number) {
for (int i = 0; i < number; i++) {
ListNode new_node = new ListNode(i);
head = headInsert(head, new_node);
head = tailInsert(head, new_node);
}
return head;
}
|
综合练习
public ListNode insertNode(ListNode head, ListNode node, int position) {
if (head == null) {
return node;
}
int length = getListLength(head);
if (position > length + 2 || position < 1) {
System.out.println("位置参数越界");
return head;
}
ListNode P = head;
for (int i = 0 ; i < position; i++) {
P = P.getNext();
}
headInsert(P, node);
return head;
}
|
链表的增删改查 - 查
先来看看链表的查询，对于单链表来说，一定是从头结点逐个向后访问，因此，头结点是一定不可以丢掉的。
我们写一个遍历函数，同时输出链表长度
public int getListLength(ListNode head) {
int length = 0;
ListNode node = head;
while(node != null) {
length++;
System.out.printf("%d ", node.getData());
node = node.getNext();
}
return length;
}
|
这里可以看出，传入遍历函数的结点不同，因为头插法返回的都是头结点，此时的 head 可以说是没变，直接传入。而对于尾插法来说，我这里的处理是用了一个 L 结点存储头结点信息，所以传入遍历函数的是 L 结点。
System.out.println("链表长度为: " + (test.getListLength(head) - 1));
System.out.println("链表长度为: " + (test.getListLength(L) - 1));
|
链表的增删改查 - 删
对于删除来说还是挺好办的，处理以下特殊位置，其他位置遍历到前驱结点，然后将前驱结点的 next 直接设置为删除结点的后置结点。
表头
这种情况只需要 head = head.getNext();
表尾和其他
遍历到删除结点的前驱就可以进行操作了
public ListNode deleteNode(ListNode head, int position) {
if (head == null) {
return null;
}
int length = getListLength(head);
if (position > length + 1 || position < 1) {
System.out.println("位置参数越界");
return head;
}
if (position == 1) {
head.setNext(head.getNext().getNext());
}
ListNode P = head;
for (int i = 0; i < position - 1; i++) {
P = P.getNext();
}
P.setNext(P.getNext().getNext());
return head;
}
|
链表的增删改查 - 改
改也是水到渠成，同样的操作，只不过这次直接遍历到需要修改的结点即可
public ListNode changeNode(ListNode head, int data, int position) {
if (head == null) {
return null;
}
int length = getListLength(head);
if (position > length + 1 || position < 1) {
System.out.println("位置参数越界");
return head;
}
ListNode P = head;
for (int i = 0; i < position; i++) {
P = P.getNext();
}
P.setData(data);
return head;
}
|
