1、继续学习单链表，终于摆脱数组的魔爪了，单链表分为数据域（前突）和引用域（指针域）（后继），还有一个头结点（就好比一辆火车，我们只关心火车头，不关心其它车厢，只需知晓车头顺藤摸瓜即可），头结点没有前突，尾结点没有后继，注意不是前仆后继。
public class Node {//包装车厢
/**
* 人无完人，如有bug，还请斧正
*/
public long data;// 数据域
public Node next;// 指针域，后指针
public Node previous;// 指针域，前指针
public Node(long value) {// 构造函数
this.data = value;
}
public void display() {
System.out.print(data + " ");
}
}
//单链表,头结点插入
public class LinkList {
private Node first;// 火车头，保存头结点的一个指向 public LinkList() {// 初始化
first = null;
} public static void main(String[] args) {
LinkList ll = new LinkList();
ll.insert(4);// 添加
ll.insert(57);
ll.insert(32);
ll.insert(68); ll.display();// 先进后出 ll.delete(32);// 删除32
System.out.println("");
System.out.println("--------");
ll.display(); System.out.println("");
System.out.println("--------"); ll.deleteFirst();// 删除头结点
ll.display(); System.out.println("");
System.out.println("--------");
Node node = ll.find(4);// 查找4
node.display();
} public Node deleteFirst() {// 删除头结点
first = first.next;// 头结点为头结点的下一个
return first;
} public Node find(long value) {// 按值查找，返回null或索引值
Node current = first;// 从头结点开始 while (current.data != value) { if (current.next == null) {// 尾结点后继为null
return null;
}
current = current.next;
}
return current;// 找到返回
} public Node delete(long value) {// 删除任意结点
Node current = first;
Node previous = first; while (current.data != value) {
if (current.next == null) {// 没有找到
return null;
}
previous = current;// 保存邻近的两个结点
current = current.next;
} if (current == first) {// 第一个结点
first = first.next;
} else {// 后面的结点
previous.next = current.next;// 上一个结点的下一个变为当前结点的下一个，当前结点删除
}
return current;// 结点类，返回结点类型
} public void insert(long value) {// 在头结点之后插入
Node node = new Node(value);// 创建新的结点
// 这里深深体会一下精妙之处，first保存着一个指向
node.next = first;// 图示第一步
first = node;// 图示第二步
} public void display() {// 显示
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
}
}
单链表
单链表时只能实现头部依次插入数据，为了弥补这个局限性，所以我们得学习双端链表，即链表中保存着对最后一个链结点引用的链表。
2、双端链表
//双端链表，头尾结点都可以插入
public class FirstLastLinkList {
private Node first;// 火车头,保存头结点的一个指向第一个node
private Node last;// 火车尾，保存头结点的一个指向最后一个node public FirstLastLinkList() {
first = null;
} public static void main(String[] args) {
FirstLastLinkList fll = new FirstLastLinkList(); fll.insertLast(26);
fll.insertLast(24);
fll.insertLast(65);
fll.insertLast(17);
fll.display();// 先进先出 System.out.println("");
System.out.println("--------"); fll.deleteFirst();
fll.display(); System.out.println("");
System.out.println("--------");
} public Node deleteFirst() {// 删除头结点
if (first.next == null) {
last = null;// 没有结点
}
first = first.next;
return first;
} public Node find(long value) {// 查找
Node current = first; while (current.data != value) { if (current.next == null) {
return null;
}
current = current.next;
}
return current;
} public Node delete(long value) {// 删除任意结点
Node current = first;
Node previous = first; while (current.data != value) {
if (current.next == null) {// 没有找到
return null;
}
previous = current;
current = current.next;
} if (current == first) {// 第一个结点
first = first.next;
} else {// 后面的结点
previous.next = current.next;
}
return current;
} public void insert(long value) {// 在头结点插入
Node node = new Node(value);// 创建新的结点
if (isEmpty()) {
last = node;
}
node.next = first;
first = node;
} public void insertLast(long value) {// 在尾结点插入
Node node = new Node(value);
if (isEmpty()) {// 为空
first = node;
} else {// 不为空
last.next = node;// 图示1
}
last = node;// 图示2
} public boolean isEmpty() {// 是否空
return first == null;
} public void display() {// 显示
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
}
}
双端链表
3、双向链表，Node就会多一个属性previous，每个结点除了保存对下一个结点的引用，同时还保存着对前一个结点的引用。
//双向链表，头尾结点都可以插入和删除
public class DoubleLinkList {
private Node first;// 火车头
private Node last;// 火车尾 public DoubleLinkList() {
first = null;
} public static void main(String[] args) {
DoubleLinkList dll = new DoubleLinkList();
dll.insertLast(342);
dll.insertLast(54);
dll.insertLast(24);
dll.display(); System.out.println("");
System.out.println("--------"); while (!dll.isEmpty()) {
dll.deleteFirst();
dll.display();
System.out.println("");
System.out.println("--------");
} System.out.println("");
System.out.println("--------"); System.out.println("");
System.out.println("--------");
} public Node deleteFirst() {// 从头结点开始删除
if (first.next == null) {// 判断头结点是否有下一个结点
last = null;// 没有结点
} else {
first.next.previous = null;// 设置头结点的下一个结点的previous为null
}
first = first.next;
return first;
} public Node deleteLast() {// 从尾结点开始删除
if (first.next == null) {// 头结点后面没有其它结点，当前为最后一个结点
first = null;
} else {
last.previous.next = null;// 设置尾结点的前一个结点的next为null
}
last = last.previous;
return last;
} public Node find(long value) {// 查找
Node current = first; while (current.data != value) { if (current.next == null) {
return null;
}
current = current.next;
}
return current;
} public Node delete(long value) {// 删除任意结点
Node current = first;
// 不需要临时的指针域
while (current.data != value) {
if (current.next == null) {// 没有找到
return null;
}
current = current.next;
}
if (current == first) {// 第一个结点
first = first.next;
} else {// 后面的结点
current.previous.next = current.next;
}
return current;
} public void insert(long value) {// 在头结点之后插入
Node node = new Node(value);// 创建新的结点
if (isEmpty()) {// 要对链表进行判断，为空则设置尾结点为新添加的结点
last = node;
} else {
first.previous = node;// 不为空，需要设置头结点前一个结点为新添加的结点
}
node.next = first;
first = node;
} public void insertLast(long value) {// 在尾结点之后插入
Node node = new Node(value);// 创建新的结点
if (isEmpty()) {// 为空，直接设置头结点为新添加的结点
first = node;
} else {
last.next = node;// 设置尾结点的后一个结点为新添加的结点，
}
node.previous = last;// 新添加的前一个结点为新添加的结点
last = node;
} public boolean isEmpty() {// 是否空
return first == null;
} public void display() {// 显示
Node current = first;
while (current != null) {
current.display();
current = current.next;
}
}
}
双向链表
删除后JVM自动回收垃圾
