一、单链表基本概念
单链表是一种链式存取的数据结构，用一组地址任意的存储单元（一般是非连续存储单元）存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素data + 指针next(指示后继元素存储位置)。其存储结构如图：
二、JAVA实现单链表
数据结构：
单链表有一个属性head和一些重要的方法，head为链表结点Node类的实例。Node类中包含成员变量：data，next。data为当前节点的数据域，next为指针域，指向下一个结点。
1、结点
1 class Node{ 2 int data; 3 Node next=null; 4 public Node(int data){ 5 this.data=data; 6 } 7 public Node(){} 8 public void display() { 9 System. out.print(this.data + " "); //结点打印函数 10 } 11 }
2、单链表
1 public class linkList { 2 Node head=new Node(); 3 //各种方法的实现代码 4 }
函数
1、链表添加元素之头插
每次来了新元素将其插入到头结点之后
1 public void insertHead(int val){ 2 Node newnode=new Node(val); 3 if(head.next!=null){ 4 newnode.next=head.next; 5 } 6 head.next=newnode; 7 }
2、链表添加元素之尾插
每次来了新元素将其插入到链表最后位置
1 public void insertTail(int val){ 2 Node newnode=new Node(val); 3 Node walkPointer=head; 4 while(walkPointer.next!=null){ 5 walkPointer=walkPointer.next; 6 } 7 walkPointer.next=newnode; 8 }
3、任意位置插入
1 public void insert(int pos,int val){ 2 int index=0; 3 if(pos>=0&&pos<=this.getLength()){ 4 Node walkPointer=head; 5 while(index!=pos){ 6 walkPointer=walkPointer.next; 7 index++; 8 } 9 Node newnode=new Node(val); 10 newnode.next=walkPointer.next; 11 walkPointer.next=newnode; 12 } 13 }
4、获取链表长度
1 public int getLength(){ 2 int length=0; 3 Node walkPointer=head; 4 while(walkPointer.next!=null){ 5 walkPointer=walkPointer.next; 6 length++; 7 } 8 return length; 9 }
5、删除指定结点(头指针未知)：实质用该结点代替其next结点
1 public boolean delete(Node delnode){ 2 if(delnode==null||delnode.next==null){ 3 return false; 4 } 5 delnode=delnode.next; 6 return true; 7 }
6、遍历链表
1 public void print() { 2 Node walkPointer=head; 3 System.out.println("**链表结点遍历**"); 4 while(walkPointer.next!=null){ 5 walkPointer=walkPointer.next; 6 System.out.print(walkPointer.data + " "); 7 } 8 System.out.println(); 9 }
7、链表逆置
之前遇到一道题目，需要将链表元素从尾到头创建ArrayList数组的题目，这里相同的思路，只不过是逆序输出创建新的链表。
两者不同之处在于：对于非递归的方式，链表逆序输出创建新数组时，采用头插的方式相对费时，需要将第一个元素之后的元素后移；而链表逆序输出创建新链表时，采用头插的方式相对快速，只要找到头结点即可一步插入。相反的，对于递归的方式，链表逆序输出创建新数组时，采用尾插的方式相比创建新链表要省时。
思路1：（递归）将链表结点的数据顺序取出存储在栈中——从栈中pop元素采用尾插的方式建立新链表（链表的尾插比较费时，需要遍历到链表最后一个元素才能插入元素）
public linkList reverse1(){ linkList list=new linkList(); Stack<Integer> stack=new Stack<Integer>(); Node walkPointer=head.next; while(walkPointer!=null){ stack.push(walkPointer.data); walkPointer=walkPointer.next; } while(!stack.empty()){ list.insertTail(stack.pop()); } return list; }
思路2：（非递归）声明新链表，将原链表元素顺序取出，同时采用头插的方式插入到新链表中（链表的头插相对于尾插耗时更小）
1 public linkList reverse(){ 2 linkList list=new linkList(); 3 Node walkPointer=head.next; 4 Node temp=new Node(); 5 while(walkPointer!=null){ 6 list.insertHead(walkPointer.data); 7 walkPointer=walkPointer.next; 8 } 9 return list; 10 }
整体代码（含测试）
1 package struct; 2 3 import java.util.Stack; 4 5 class Node{ 6 int data; 7 Node next=null; 8 public Node(int data){ 9 this.data=data; 10 } 11 public Node(){} 12 public void display() { 13 System. out.print(this.data + " "); //结点打印函数 14 } 15 } 16 public class linkList { 17 Node head=new Node(); 18 //头插 19 public void insertHead(int val){ 20 Node newnode=new Node(val); 21 if(head.next!=null){ 22 newnode.next=head.next; 23 } 24 head.next=newnode; 25 } 26 27 //尾插 28 public void insertTail(int val){ 29 Node newnode=new Node(val); 30 Node walkPointer=head; 31 while(walkPointer.next!=null){ 32 walkPointer=walkPointer.next; 33 } 34 walkPointer.next=newnode; 35 } 36 37 //获得链表长度 38 public int getLength(){ 39 int length=0; 40 Node walkPointer=head; 41 while(walkPointer.next!=null){ 42 walkPointer=walkPointer.next; 43 length++; 44 } 45 return length; 46 } 47 48 //任意位置插入 49 public void insert(int pos,int val){ 50 int index=0; 51 if(pos>=0&&pos<=this.getLength()){ 52 Node walkPointer=head; 53 while(index!=pos){ 54 walkPointer=walkPointer.next; 55 index++; 56 } 57 Node newnode=new Node(val); 58 newnode.next=walkPointer.next; 59 walkPointer.next=newnode; 60 } 61 } 62 63 //链表的逆置（非递归，同从尾到头构建列表，链表的头插复杂度比列表头插低很多） 64 public linkList reverse(){ 65 linkList list=new linkList(); 66 Node walkPointer=head.next; 67 Node temp=new Node(); 68 while(walkPointer!=null){ 69 list.insertHead(walkPointer.data); 70 walkPointer=walkPointer.next; 71 } 72 return list; 73 //笨方法 74 // Node preNode=head; 75 // Node walkPointer=head.next; 76 // head.next=null; 77 // Node nextNode=new Node(); 78 // while(walkPointer!=null){ 79 // nextNode=walkPointer.next; 80 // walkPointer.next=preNode; 81 // preNode=walkPointer; 82 // walkPointer=nextNode; 83 // } 84 // list.head.next=preNode; 85 // return list; 86 } 87 88 //链表的逆置（递归，使用栈。类似于从尾到头输出列表） 89 public linkList reverse1(){ 90 linkList list=new linkList(); 91 Stack<Integer> stack=new Stack<Integer>(); 92 Node walkPointer=head.next; 93 while(walkPointer!=null){ 94 stack.push(walkPointer.data); 95 walkPointer=walkPointer.next; 96 } 97 while(!stack.empty()){ 98 list.insertTail(stack.pop()); 99 } 100 return list; 101 } 102 103 //删除指定结点(头指针未知)，实质用该结点代替其next结点 104 public boolean delete(Node delnode){ 105 if(delnode==null||delnode.next==null){ 106 return false; 107 } 108 delnode=delnode.next; 109 return true; 110 } 111 112 //打印遍历 113 public void print() { 114 Node walkPointer=head; 115 System.out.println("**链表结点遍历**"); 116 while(walkPointer.next!=null){ 117 walkPointer=walkPointer.next; 118 System.out.print(walkPointer.data + " "); 119 } 120 System.out.println(); 121 } 122 @SuppressWarnings("null") 123 public static void main(String []args){ 124 linkList list=new linkList(); 125 list.insertHead(12); 126 list.insertHead(15); 127 list.insertHead(2); 128 list.insertHead(3); 129 list.insert(0,4); 130 list.print(); 131 System.out.println("链表长度"); 132 System.out.println(list.getLength()); 133 System.out.println("！！链表转置后的头结点数据！！"); 134 linkList returnlist=new linkList(); 135 returnlist=list.reverse(); 136 returnlist.print(); 137 returnlist=list.reverse1(); 138 returnlist.print(); 139 } 140 }