JAVA之数据结构——单链表
一、单链表的概念
链表是最基本的数据结构，其存储的你原理图如下图所示
上面展示的是一个单链表的存储原理图，简单易懂，head为头节点，他不存放任何的数据，只是充当一个指向链表中真正存放数据的第一个节点的作用，而每个节点中都有一个next引用，指向下一个节点，就这样一节一节往下面记录，直到最后一个节点，其中的next指向null。
链表有很多种，比如单链表，双链表等等。我们就对单链表进行学习，其他的懂了原理其实是一样的。
节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。下面图是具体的说明：
二、用java实现单链表
语言只是一种工具，数据结构真正体会的是那种思想，这句话确实是这样，不管用什么写，其思想是不改变的。以前使用的是C++,现在用的是java，一步步来实现。
1、常用操作
查找
插入
删除
查找：
（1）按照索引查找index位置上的节点：从头节点head开始依次向下找到第index位置的节点。
（2）找到指定数据的索引位置：查找是否有节点中存放的数据与给定的数据相同，若有则返回节点的位置，没有返回-1.从头节点开始，一一对比。
插入：
（1）头插法：每次插入的新节点作为链表的头节点
（2）尾插法：在链表的尾部插入心节点
（3）在指定的索引位置插入：将值为element的新节点插入到链表index的位置，首先找到位置index-1位置的节点，生成一个新节点newNode,让index-1的next指向新节点，新节点指向原来index.
删除
将链表的第index个节点删除。先找到链表中index-1处的节点，让index-1处的节点指向原来index+1的节点，并释放index处的节点。
代码实现1：
public class LinkList<T>{
private class Node//节点类
{
private T data;
private Node next;
public Node()
{
}
public Node(T data,Node next)
{
this.data = data;
this.next = next;
}
}
private Node head;//指向链表头节点的引用变量
private Node tail;//指向链表尾节点的引用变量
int size;//链表中当前总节点数
//生成链表对象是一个空表
public LinkList()
{
head = null;
tail = null;
}
//生成链表对象时有一个头节点 （有参构造器）
public LinkList (T data)
{
head = new Node(data,null);//指定一个头节点的数据域值为data,不指向其他节点
tail = head;
size++;
}
//返回链表的长度
public int length()
{
return size;
}
//获取指定位置的元素
public T getElement(int index)
{
return findNodeByIndex(index).data;
}
//查找 指定索引位置的节点
public Node findNodeByIndex(int index)
{
if(index < 0 || index > size-1)
{
throw new IndexOutOfBoundsException("线性表索引越界");
}
Node current = head;//从头节点开始下移遍历
for (int i = 0;i < size &¤t.next!=null;i++,current = current.next)
{
if(i == index)
{
return current;
}
}
return null;
}
//查找 指定元素的位置(查找数据域存放的是element的节点位置)
public int findIndexByElement(T element)
{
Node current = head;//从第一个节点开始查找对比数据
for(int i=0; i<size&¤t.next!=null;i++,current=current.next)
{
if(current.data.equals(element))
return i;
}
return -1;
}
//插入 在指定位置插入一个元素
public void insert(int index,T element)
{
if(index < 0 || index > size)
{
throw new IndexOutOfBoundsException("线性表索引越界");
}
if(head == null)//如果链表为空，直接调用add方法
{
add(element);
}
else //链表不为空时
{
if(index==0)//在链表头插入
{
addAtHead(element);
}
else
{
Node prev = findNodeByIndex(index-1);//找到要插入位置的前一个节点
prev.next = new Node(element,prev.next);//插入后prev的next指向新节点，新节点的next指向原来prev的下一个节点
size++;
}
}
}
//插入 尾插法在每次在链表尾添加新节点
public void add(T element)
{
if(head==null)
{
head = new Node(element,null);
tail = head;
}
else
{
Node newNode = new Node(element,null);
tail.next = newNode;
tail = newNode;
}
size++;
}
//插入 头插法在链表头部加入新节点
public void addAtHead(T element)
{
//在头部插入新节点，就是让新节点的next指向原来的head,让新节点作为链表的头节点
head = new Node(element,head);
//newNode.next = head;
//head = newNode;
//如果插入之前是空链表
if(tail==null)
{
tail=head;
}
}
//删除指定位置的节点 返回删除节点中的元素值
public T delete (int index)
{
Node deleteNode = null;
if(index<0||index>size-1)
{
throw new IndexOutOfBoundsException("线性表索引越界");
}
if(index==0)//删除头节点
{
deleteNode = head;
head = head.next;
}
else
{
Node prev = findNodeByIndex(index-1);//获取要删除的节点的前一个节点
deleteNode = prev.next;//要删除的节点就是prev的next指向的节点
prev.next=deleteNode.next;//删除以后prev的next指向被删除节点之前所指向的next
deleteNode.next = null;
}
return deleteNode.data;
}
//删除 链表中最后一个元素
public T removeLast()
{
return delete(size-1);
}
//清除链表中所有的元素
public void clear()
{
head = null;
tail = null;
size = 0;
}
//判断链表是否为空
public boolean isEmpty()
{
return size==0;
}
public String toString()//链表的输出 重写toString方法
{
if(isEmpty())
{
return "[]";
}
else
{
StringBuilder sb = new StringBuilder("[");//使用StringBuilder类
for(Node current = head;current != null ; current = current.next)//从head开始遍历
{
sb.append(current.data.toString()+",");//把节点的数据拼接起来
}
int len = sb.length();
return sb.delete(len-1,len).append("]").toString();//把最后一个元素的，删除然后加上]
}
}
}
测试
public class LinkListTest
{
public static void main(String[] args)
{
LinkList<String> list = new LinkList<String>();
list.add("aa");
list.add("bb");
list.add("cc");
System.out.println(list);
list.addAtHead("11");
list.insert(1,"22");
System.out.println(list);
list.delete(2);
System.out.println(list);
list.clear();
System.out.println(list);
}
}
输出结果：
[aa,bb,cc]
[11,22,aa,bb,cc]
[11,22,bb,cc]
[]
实例二：
单链表结构：
Java中单链表采用Node实体类类标识，其中data为存储的数据，next为下一个节点的指针：
package com.algorithm.link; /** * 链表结点的实体类 * @author bjh * */ public class Node { Node next = null;//下一个结点 int data;//结点数据 public Node(int data){ this.data = data; } }
三、链表常见操作：
package com.algorithm.link; import java.util.Hashtable; /** * 单链表常见算法 * @author bjh * */ public class MyLinkedList { /**链表的头结点*/ Node head = null; /** * 链表添加结点: * 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点 * @param data */ public void addNode(int data){ Node newNode = new Node(data); if(head == null){ head = newNode; return; } Node temp = head; while(temp.next != null){ temp = temp.next; } temp.next = newNode; } /** * 链表删除结点: * 把要删除结点的前结点指向要删除结点的后结点，即直接跳过待删除结点 * @param index * @return */ public boolean deleteNode(int index){ if(index<1 || index>length()){//待删除结点不存在 return false; } if(index == 1){//删除头结点 head = head.next; return true; } Node preNode = head; Node curNode = preNode.next; int i = 1; while(curNode != null){ if(i==index){//寻找到待删除结点 preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点 return true; } //当先结点和前结点同时向后移 preNode = preNode.next; curNode = curNode.next; i++; } return true; } /** * 求链表的长度 * @return */ public int length(){ int length = 0; Node curNode = head; while(curNode != null){ length++; curNode = curNode.next; } return length; } /** * 链表结点排序,并返回排序后的头结点: * 选择排序算法,即每次都选出未排序结点中最小的结点，与第一个未排序结点交换 * @return */ public Node linkSort(){ Node curNode = head; while(curNode != null){ Node nextNode = curNode.next; while(nextNode != null){ if(curNode.data > nextNode.data){ int temp = curNode.data; curNode.data = nextNode.data; nextNode.data = temp; } nextNode = nextNode.next; } curNode = curNode.next; } return head; } /** * 打印结点 */ public void printLink(){ Node curNode = head; while(curNode !=null){ System.out.print(curNode.data+" "); curNode = curNode.next; } System.out.println(); } /** * 去掉重复元素: * 需要额外的存储空间hashtable，调用hashtable.containsKey()来判断重复结点 */ public void distinctLink(){ Node temp = head; Node pre = null; Hashtable<Integer, Integer> hb = new Hashtable<Integer, Integer>(); while(temp != null){ if(hb.containsKey(temp.data)){//如果hashtable中已存在该结点，则跳过该结点 pre.next = temp.next; }else{//如果hashtable中不存在该结点，将结点存到hashtable中 hb.put(temp.data, 1); pre=temp; } temp = temp.next; } } /** * 返回倒数第k个结点, * 两个指针，第一个指针向前移动k-1次，之后两个指针共同前进， * 当前面的指针到达末尾时，后面的指针所在的位置就是倒数第k个位置 * @param k * @return */ public Node findReverNode(int k){ if(k<1 || k>length()){//第k个结点不存在 return null; } Node first = head; Node second = head; for(int i=0; i<k-1; i++){//前移k-1步 first = first.next; } while(first.next != null){ first = first.next; second = second.next; } return second; } /** * 查找正数第k个元素 */ public Node findNode(int k){ if(k<1 || k>length()){//不合法的k return null; } Node temp = head; for(int i = 0; i<k-1; i++){ temp = temp.next; } return temp; } /** * 反转链表，在反转指针钱一定要保存下个结点的指针 */ public void reserveLink(){ Node curNode = head;//头结点 Node preNode = null;//前一个结点 while(curNode != null){ Node nextNode = curNode.next;//保留下一个结点 curNode.next = preNode;//指针反转 preNode = curNode;//前结点后移 curNode = nextNode;//当前结点后移 } head = preNode; } /** * 反向输出链表，三种方式： * 方法一、先反转链表，再输出链表，需要链表遍历两次 * 方法二、把链表中的数字放入栈中再输出，需要维护额外的栈空间 * 方法三、依据方法2中栈的思想，通过递归来实现，递归起始就是将先执行的数据压入栈中， 再一次出栈 */ public void reservePrt(Node node){ if(node != null){ reservePrt(node.next); System.out.print(node.data+" "); } } /** * 寻找单链表的中间结点： * 方法一、先求出链表的长度，再遍历1/2链表长度，寻找出链表的中间结点 * 方法二、： * 用两个指针遍历链表，一个快指针、一个慢指针， * 快指针每次向前移动2个结点，慢指针一次向前移动一个结点， * 当快指针移动到链表的末尾，慢指针所在的位置即为中间结点所在的位置 */ public Node findMiddleNode(){ Node slowPoint = head; Node quickPoint = head; //quickPoint.next == null是链表结点个数为奇数时，快指针已经走到最后了 //quickPoint.next.next == null是链表结点数为偶数时，快指针已经走到倒数第二个结点了 //链表结点个数为奇数时,返回的是中间结点；链表结点个数为偶数时， 返回的是中间两个结点中的前一个 while(quickPoint.next != null && quickPoint.next.next != null){ slowPoint = slowPoint.next; quickPoint = quickPoint.next.next; } return slowPoint; } /** * 判断链表是否有环： * 设置快指针和慢指针，慢指针每次走一步，快指针每次走两步 * 当快指针与慢指针相等时，就说明该链表有环 */ public boolean isRinged(){ if(head == null){ return false; } Node slow = head; Node fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; if(fast == slow){ return true; } } return false; } /** * 返回链表的最后一个结点 */ public Node getLastNode(){ Node temp = head; while(temp.next != null){ temp = temp.next; } return temp; } /** * 在不知道头结点的情况下删除指定结点： * 删除结点的重点在于找出其前结点，使其前结点的指针指向其后结点，即跳过待删除结点 * 1、如果待删除的结点是尾结点，由于单链表不知道其前结点，没有办法删除 * 2、如果删除的结点不是尾结点，则将其该结点的值与下一结点交换， 然后该结点的指针指向下一结点的后续结点 */ public boolean deleteSpecialNode(Node n){ if(n.next == null){ return false; }else{ //交换结点和其后续结点中的数据 int temp = n.data; n.data = n.next.data; n.next.data = temp; //删除后续结点 n.next = n.next.next; return true; } } /** * 判断两个链表是否相交： * 两个链表相交，则它们的尾结点一定相同，比较两个链表的尾结点是否相同即可 */ public boolean isCross(Node head1, Node head2){ Node temp1 = head1; Node temp2 = head2; while(temp1.next != null){ temp1 = temp1.next; } while(temp2.next != null){ temp2 = temp2.next; } if(temp1 == temp2){ return true; } return false; } /** * 如果链表相交，求链表相交的起始点： * 1、首先判断链表是否相交，如果两个链表不相交，则求相交起点没有意义 * 2、求出两个链表长度之差：len=length1-length2 * 3、让较长的链表先走len步 * 4、然后两个链表同步向前移动，没移动一次就比较它们的结点是否相等， 第一个相等的结点即为它们的第一个相交点 */ public Node findFirstCrossPoint(MyLinkedList linkedList1, MyLinkedList linkedList2){ //链表不相交 if(!isCross(linkedList1.head,linkedList2.head)){ return null; }else{ int length1 = linkedList1.length();//链表1的长度 int length2 = linkedList2.length();//链表2的长度 Node temp1 = linkedList1.head;//链表1的头结点 Node temp2 = linkedList2.head;//链表2的头结点 int len = length1 - length2;//链表1和链表2的长度差 if(len > 0){//链表1比链表2长，链表1先前移len步 for(int i=0; i<len; i++){ temp1 = temp1.next; } }else{//链表2比链表1长，链表2先前移len步 for(int i=0; i<len; i++){ temp2 = temp2.next; } } //链表1和链表2同时前移,直到找到链表1和链表2相交的结点 while(temp1 != temp2){ temp1 = temp1.next; temp2 = temp2.next; } return temp1; } } }
四、测试类：
package com.algorithm.link; /** * 单链表操作测试类 * @author bjh * */ public class Test { public static void main(String[] args){ MyLinkedList myLinkedList = new MyLinkedList(); //添加链表结点 myLinkedList.addNode(9); myLinkedList.addNode(8); myLinkedList.addNode(6); myLinkedList.addNode(3); myLinkedList.addNode(5); //打印链表 myLinkedList.printLink(); /*//测试链表结点个数 System.out.println("链表结点个数为：" + myLinkedList.length()); //链表排序 Node head = myLinkedList.linkSort(); System.out.println("排序后的头结点为：" + head.data); myLinkedList.printLink(); //去除重复结点 myLinkedList.distinctLink(); myLinkedList.printLink(); //链表反转 myLinkedList.reserveLink(); myLinkedList.printLink(); //倒序输出/遍历链表 myLinkedList.reservePrt(myLinkedList.head); //返回链表的中间结点 Node middleNode = myLinkedList.findMiddleNode(); System.out.println("中间结点的数值为："+middleNode.data); //判断链表是否有环 boolean isRinged = myLinkedList.isRinged(); System.out.println("链表是否有环：" + isRinged); //将链表的最后一个结点指向头结点，制造有环的效果 Node lastNode = myLinkedList.getLastNode(); lastNode.next = myLinkedList.head; isRinged = myLinkedList.isRinged(); System.out.println("链表是否有环：" + isRinged); //删除指定结点 Node nk = myLinkedList.findReverNode(3); System.out.println(nk.data); myLinkedList.deleteSpecialNode(nk); myLinkedList.printLink(); //链表是否相交 //新链表 MyLinkedList myLinkedList1 = new MyLinkedList(); myLinkedList1.addNode(1); myLinkedList1.addNode(2); myLinkedList1.printLink(); System.out.println("链表一和链表二是否相交"+ myLinkedList.isCross(myLinkedList.head, myLinkedList1.head)); //把第二个链表从第三个结点开始接在第二个链表的后面，制造相交的效果 myLinkedList1.findNode(2).next = myLinkedList.findNode(3); myLinkedList1.printLink(); System.out.println("链表一和链表二是否相交"+ myLinkedList.isCross(myLinkedList.head, myLinkedList1.head)); */ //如果两个链表相交求链表相交的结点的值 MyLinkedList myLinkedList1 = new MyLinkedList(); myLinkedList1.addNode(1); myLinkedList1.addNode(2); myLinkedList1.findNode(2).next = myLinkedList.findNode(3); myLinkedList1.printLink(); Node n = myLinkedList1.findFirstCrossPoint(myLinkedList, myLinkedList1); if(n == null){ System.out.println("链表不相交"); }else{ System.out.println("两个链表相交，第一个交点的数值为：" + n.data); } } }
2.2.5、单链表进行插入排序 insertSortNode()
三、总结
基本的单链表操作就是上面这些了，自己完全手动写一写，会对单链表这种数据结构的理解有很大的帮助。当然其中比较难的是在于对链表的排序上，说难也不难，只要懂的几种排序的原理，就跟写伪代码一样，去实现即可。这里还有一些操作，大家可以动手做一做，我会在下一篇文章中讲解这些答案。
3.1、如何从链表中删除重复数据
3.2、如何找出单链表中的倒数第k个元素
3.3、如何实现链表的反转
3.4、如何从尾到头输出单链表
3.5、如何寻找单链表的中间结点
3.6、如何检测一个链表是否有环
3.7、如何在不知道头结点的情况下删除指定结点
3.8、如何判断两个链表是否相交