手写一个简单的单链表的增删改查, 本文不注重代码的严谨格式等, 仅仅是探究其实现的思想
假如我们需要添加一个数据
代码中数据结构是这样的
1 2 3 4 5 6 7 8 |
class Node {
// 存储下一个节点
Node next;
String mes;
public Node(String mes) {
this.mes = mes;
}
} |
插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public static void insert(Node n) {
Node current = rootNode;
if (current == null) {
// 第一次插入
rootNode = n;
return;
}
Node next;
while ((next = current.getNext()) != null) {
current = next; // 移动指针
}
current.setNext(n);
} |
删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public static void delete(String mes) {
Node current = rootNode;
Node next;
// 1， 2， 3， 4， 5
// 假如是要删除3， 则需要2的指针链上4
// 因为单链表找不到前驱节点， 所以需要先找到2所在的当前节点， 然后删除3，找到3所在的节点的下一个节点指向2
while ((next = current.getNext()) != null) {
if (mes.equals(next.getMes())) {
// 删除节点， 指针位置发生改变
current.setNext(next.getNext()); // 2 = 4
next.setNext(null); // 3 // 原本3的指向移除掉
return;
}
current = next;
}
} |
修改
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public static void modify(String oldMes, String newMes) {
Node current = rootNode;
Node next;
// 1， 2， 3， 4， 5
// 假如要修改的是3，改为 6
while ((next = current.getNext()) != null) {
if (oldMes.equals(current.getMes())) {
current.setMes(newMes);
return;
}
current = next;
}
} |
获取
1 2 3 4 5 6 7 8 9 |
public static void getAll() {
Node current = rootNode;
Node next;
while ((next = current.getNext()) != null) {
System.out.println(current.getMes());
current = next;
}
System.out.println(current.getMes());
} |
完整代码如下
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 |
public class MyTest {
private static Node rootNode = null;
public static void insert(Node n) {
Node current = rootNode;
if (current == null) {
// 第一次插入
rootNode = n;
return;
}
Node next;
while ((next = current.getNext()) != null) {
current = next; // 移动指针
}
current.setNext(n);
}
public static void delete(String mes) {
Node current = rootNode;
Node next;
// 1， 2， 3， 4， 5
// 假如是要删除3， 则需要2的指针链上4
// 因为单链表找不到前驱节点， 所以需要先找到2所在的当前节点， 然后删除3，找到3所在的节点的下一个节点指向2
while ((next = current.getNext()) != null) {
if (mes.equals(next.getMes())) {
// 删除节点， 指针位置发生改变
current.setNext(next.getNext()); // 2 = 4
next.setNext(null); // 3 // 原本3的指向移除掉
return;
}
current = next;
}
}
public static void modify(String oldMes, String newMes) {
Node current = rootNode;
Node next;
// 1， 2， 3， 4， 5
// 假如要修改的是3，改为 6
while ((next = current.getNext()) != null) {
if (oldMes.equals(current.getMes())) {
current.setMes(newMes);
}
current = next;
}
}
public static void getAll() {
Node current = rootNode;
Node next;
while ((next = current.getNext()) != null) {
System.out.println(current.getMes());
current = next;
}
System.out.println(current.getMes());
}
public static void main(String[] args) {
Node node = new Node("1");
Node node1 = new Node("2");
Node node2 = new Node("3");
Node node3 = new Node("4");
Node node4 = new Node("5");
insert(node);
insert(node1);
insert(node2);
insert(node3);
insert(node4);
delete("3");
modify("3", "6");
getAll();
}
}
class Node {
// 存储下一个节点
private Node next;
private String mes;
public Node(String mes) {
this.mes = mes;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String getMes() {
return mes;
}
public void setMes(String mes) {
this.mes = mes;
}
} |
好了, 增删改查的代码大致就是这些了, 在 ArrayList源码分析 中我们了解到其内部使用的是数组的结构, 或者叫顺序表的方式, 那么他们两个到底有什么区别呢 ? 或者是在使用场景上有什么区别呢 ?
首先针对数据的增删改查来说, 顺序表的内存地址是连续的, 他可以基于下标快速访问到元素,这是优点, 删除元素需要一直遍历查找到元素为止, 然后一个一个到挪动元素的位置, 消耗时间
相对于顺序表, 单链表的优点是, 内存地址是不连续的, 当前节点存在着下一个节点的引用, 直接修改节点引用即可, 复杂度相对于顺序表简单
所以查找到使用顺序表结构, 修改多使用链表的形式