本文共 3948 字，大约阅读时间需要 13 分钟。
先了解下什么是链表？通过火车的多节车厢我们来下形容链表。每节车厢都有两个信息，头节点和尾节点，当然有两头我们叫双链表。我们先来看看单向链表，就是链表中节点与节点之间只考虑头节点。
用图来表示一个简单的单向链表。
上面这个图就是一个单链表（list），一个节点（node）中分成两部分，一个用来存储数据，一个是存储下一个节点的内存地址，其实就是指针。根据指针寻找下一个节点，从而找到下一个节点的数据。本篇，我们就来学习一个单链表的基本操作。我们封装的自定义类和方法就是Java JDK中自带的ArrayList的效果。
链表基本方法封装
我们需要两个类，一个类Node.java是定义一个节点，结点有数据和指向下一个结点的内存地址。第二个是我们单链表的方法封装，我们先来看看如何插入一个结点的代码实现过程。先理解插入结点代码和打印结点方法的代码，其他删除，插入就变得容易理解。
Node.java内容
package list;/* * 链结点，相当于一个火车车厢 */public class Node { //数据域 public long data; //结点域（指针） public Node next; public Node(long value) { this.data = value; } /* * 显示结点的值 */ public void display() { System.out.print(data + " "); //加一个空格，打印效果好看 }} LinkList.java内容
package list;/* * 链表 相当于火车 */public class LinkList { //头结点 private Node first; public LinkList() { first = null; } /* * 插入一个结点方法,是在头结点之后插入 */ public void insertFirst(long value) { Node node = new Node(value); node.next = first; first = node; } /* * 打印链表结点内容 */ public void display() { Node current = first; while(current != null) { current.display(); current = current.next; } System.out.println(); }} 先看看插入结点的方法，因为我们每次插入都是在新的链表的头结点之后去插入数据。我们这里，暂时不考虑指定结点后面插入结点，我们先每次插入都是在第一个结点之后插入结点。
public void insertFirst(long value) { Node node = new Node(value); node.next = first; first = node;} 第一行是实例化一个Node对象，这个结点的数据值是value, 也就是要把新插入的结点先实例化出来。然后这个新结点指向原来存在的第一个结点。所以上面第二行把first的内存地址赋值给了node.next。第三行，因为插入了新结点，所以把新插入的结点重置为链表的头结点。下面画图来演示一下。
上面图，本来我们头结点是一个32，接下来我们在头结点之后插入一个新结点，就是上面48这个数据，插入之后的效果是这样的：48在32的后边，看箭头顺序来决定前后顺序。
下面看看链表中打印链表的方法代码
public void display() { Node current = first; while(current != null) { current.display(); current = current.next; } System.out.println();} 假如当前结点从头结点开始，开始while循环，如果当前结点不为空，就调用结点本身的display()方法，打印这个结点本身的数据。打印完一个结点之后，把当前结点指向下一个结点重置为当前结点，继续判断是否为空和打印。
下面，我们来写一个测试LinkList.java的代码，插入五个结点，并打印结点看看效果。
package list;public class TestLinkList { public static void main(String[] args) { LinkList ll = new LinkList(); ll.insertFirst(24); ll.insertFirst(32); ll.insertFirst(48); ll.insertFirst(57); ll.insertFirst(19); ll.display(); }} 运行效果
19 57 48 32 24
这个打印效果和对应插入的顺序，确实是每次都在头结点之后插入新结点。
根据上面的基础，我们来写删除结点方法和查找结点方法。
package list;/* * 链表 相当于火车 */public class LinkList { //头结点 private Node first; public LinkList() { first = null; } /* * 插入一个结点方法,是在头结点之后插入 */ public void insertFirst(long value) { Node node = new Node(value); node.next = first; first = node; } /* * 打印链表结点内容 */ public void display() { Node current = first; while(current != null) { current.display(); current = current.next; } System.out.println(); } /* * 查找方法 */ 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 deleteFirst() { Node tmp = first.next; first.next = tmp.next; return tmp; }} 测试类代码
package list;public class TestLinkList { public static void main(String[] args) { LinkList ll = new LinkList(); ll.insertFirst(24); ll.insertFirst(32); ll.insertFirst(48); ll.insertFirst(57); ll.insertFirst(19); ll.display(); //查找48这个结点 Node node = ll.find(48); node.display(); System.out.println(); //删除结点 ll.deleteFirst(); ll.display(); }} 测试结果
19 57 48 32 24 48 19 48 32 24
下面继续写一个删除方法，根据data的值去删除这个结点。
/* * 删除方法，根据数据来删除结点 */ public Node delete(long value) { //当前结点从头结点开始 Node current = first; //表示当前结点的前面一个结点 Node previous = first; //删除也是根据查找的逻辑先去找到才能删除 while(current.data != value) { // 如果结点中的值不匹配，需要判断当前结点下一个是否为空，如果为空就说明查找不到改数据 if(current.next == null) { return null; //查找不到 } //找到了就进行删除，删除的逻辑是当前找到这个结点是要删除 //只需要把当前结点前面一个结点.next指向了当前结点后面一个结点 previous = current; current = current.next; } //如果一开始就找到了 if(current == first) { first = first.next; }else { previous.next = current.next; } return current; }
转载地址：http://akows.baihongyu.com/