**单链表：**又名单向链表、线性链表，是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。
单向链表的数据结构可以分为两部分：数据域和指针域，数据域存储数据，指针域指向下一个储存节点的地址。
下面以具体程序看看单链表的各种操作：
基本操作：头插法、尾插法、指定位置插入元素、求长度、求倒数第k个元素、链表逆置。
class Link{ Entry head = new Entry(); /** 节点类，用于节点初始化 */ class Entry{ int data; Entry next; public Entry() { data = -1; next = null; } public Entry(int data) { this.data = data; next = null; } } /** 头插法 */ public void insertHead(int data) { Entry cur = new Entry(data); cur.next = head.next; head.next = cur; } /** 尾插法 */ public void insertTail(int data) { Entry cur = head; // 寻找最后一个节点 while (cur.next != null) { cur = cur.next; } // 插入新节点 Entry entry = new Entry(data); cur.next = entry; } /** 求长度 */ public int getLength() { int len = 0; Entry cur = head; while (cur.next != null) { cur = cur.next; len++; } return len; } /** 指定位置插入 */ public void insertPos(int data, int pos) { // 判断指针合法性 if (pos < 0 || pos > getLength()) { return; } Entry cur = head; // 找到要插入的位置 for (int x = 0; x < pos; x++) { cur = cur.next; } // 插入新节点 Entry entry = new Entry(data); entry.next = cur.next; cur.next = entry; } /** 单链表的逆置方式一 */ public void reverse() { Entry cur = head; // 如果只有表头或者只有一个结点，则不交换 if(cur.next == null || cur.next.next == null ) { return; } // 定义一个指针指向第二个结点 Entry pos = cur.next.next; // 第一个结点逆置后将是最后一个结点，故令它的next为null， cur.next.next = null; while (pos != null) { Entry temp = pos.next; // 将指针所指向的结点插入头结点之后 pos.next = cur.next; cur.next = pos; // 指针指向下一个结点 pos = temp; } } /** 单链表的逆置方式二 */ public Entry reverse1(){ Entry newHead = null; Entry prev = null; Entry cur = head; // 找到逆置后的链表的头结点 while(cur != null){ Entry curNext = cur.next; if(curNext == null){ newHead = cur; } // 依次转置 cur.next = prev; prev = cur; cur = curNext; } return newHead; } /** 求倒数第k个结点方式一 */ public int searchPos1(int k) { // 判断k的合法性 if (k <= 0 || k > getLength()) { return -1; } Entry cur = head.next; // 通过从前往后依次遍历的方式找到对应元素 for (int x = 0; x <= getLength() - k; x++) { cur = cur.next; } return cur.data; } /** 求倒数第k个结点方式二 */ public int searchPos2(int k) { // 判断k的合法性 if (k <= 0 || k > getLength()) { return -1; } // 定义两个指针 Entry cur1 = head; Entry cur2 = head; // 第一个指针先遍历k-1步 while (k - 1 > 0) { if (cur1.next != null) { cur1 = cur1.next; --k; }else { return -1; } } // 而后两个指针同时遍历，等到第一个指针遍历完整个链表时第二个指针正好到倒数第k位置 while (cur1.next != null) { cur1 = cur1.next; cur2 = cur2.next; } return cur2.data; } /** 输出 */ public void print() { Entry cur = head.next; while(cur != null) { System.out.print(cur.data + "\t"); cur = cur.next; } System.out.println(); } /** 逆置输出 */ public void show2(Entry entry){ Entry cur = entry; while(cur.next != null){ System.out.print(cur.data + "\t"); cur = cur.next; } System.out.println(); } ｝用一个例子验证以上程序是否正确：
public class LinkTest { public static void main(String [] args) { Link link = new Link(); // 利用头插法给链表动态赋值 for (int x = 0; x < 10; x++) { link.insertHead(x); } System.out.println("长度是" + link.getLength()); System.out.println(link.searchPos1(3)); System.out.println(link.searchPos2(3)); link.print(); link.show2(link.reverse1()); } }以上程序的输出结果是：
长度是10 2 2 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9