自己动手写一个单链表_JAVA_编程开发_程序员俱乐部

文章有不当之处，欢迎指正，如果喜欢微信阅读，你也可以关注我的微信公众号：好好学java，获取优质学习资源。

一、概述

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢

使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。

二、图解

下图就是最简单最一般的单向链表：

新增节点：

将值为element的新节点插入到第index的位置上。

首先要先找到索引为index-1的节点，然后生成一个数据为element的新节点newNode，并令index-1处节点的next指向新节点，新节点的next指向原来index处的节点。

删除节点：

删除第index个节点，第index节点是由index-1出的节点引用的，因此删除index的节点要先获取index-1处的节点，然后让index-1出节点的next引用到原index+1处的节点，并释放index处节点即可。

三、单向链表的Java实现

下面的程序分别实现了线性表的初始化、获取线性表长度、获取指定索引处元素、根据值查找、插入、删除、清空等操作。

monospace; border-radius: 0px; color: #a9b7c6; padding: 0.5em; display: block !important; white-space: pre !important; overflow: auto !important;" class="hljs java">public?class?LinkList<T>?{??
????//?定义一个内部类Node，代表链表的节点??
????private?class?Node?{??
????????private?T?data;//?保存数据??
????????private?Node?next;//?指向下个节点的引用??
????????//?无参构造器??
????????function">public?Node()?{??
????????}??
????????//?初始化全部属性的构造器??
????????public?Node(T?data,?Node?next)?{??
????????????this.data?=?data;??
????????????this.next?=?next;??
????????}??
????}??
????private?Node?header;//?保存头结点??
????private?Node?tail;//?保存尾节点??
????private?int?size;//?保存已含有的节点数??
????//?创建空链表??
????public?LinkList()?{??
????????header?=?null;??
????????tail?=?null;??
????}??
????//?已指定数据元素创建链表，只有一个元素??
????public?LinkList(T?element)?{??
????????header?=?new?Node(element,?null);??
????????//?只有一个节点，header,tail都指向该节点??
????????tail?=?header;??
????????size++;??
????}??
????//?返回链表的长度??
????public?int?length()?{??
????????return?size;??
????}??
????//?获取指定索引处的元素??
????public?T?get(int?index)?{??
????????return?this.getNodeByIndex(index).data;??
????}??
????//获取指定位置的节点??
????private?Node?getNodeByIndex(int?index){??
????????if(index?<?0?||?index?>?size-1){??
????????????throw?new?IndexOutOfBoundsException("索引超出线性表范围");??
????????}??
????????Node?current?=?header;//从header开始遍历??
????????for(int?i=0;?i<size?&&?current!=null;?i++,current=current.next){??
????????????if(i?==?index){??
????????????????return?current;??
????????????}??
????????}??
????????return?null;??
????}??
????//按值查找所在位置??
????public?int?locate(T?element){??
????????Node?current?=?header;??
????????for(int?i=0;?i<size?&&?current!=null;?i++,?current=current.next){??
????????????if(current.data.equals(element)){??
????????????????return?i;??
????????????}??
????????}??
????????return?-1;??
????}??
????//指定位置插入元素??
????public?void?insert(T?element,?int?index){??
????????if(index?<?0?||?index?>?size){??
????????????throw?new?IndexOutOfBoundsException("索引超出线性表范围");??
????????}??
????????//如果是空链表??
????????if(header?==?null){??
????????????add(element);??
????????}??
????????else{??
????????????//当index为0时，即在链表头处插入??
????????????if(0?==?index){??
????????????????addAtHead(element);??
????????????}??
????????????else{??
????????????????Node?prev?=?getNodeByIndex(index?-?1);//获取前一个节点??
????????????????//让prev的next指向新节点，新节点的next指向原来prev的下一个节点??
????????????????prev.next?=?new?Node(element,?prev.next);??
????????????????size++;??
????????????}??
????????}??
????}??
????//在尾部插入元素??
????public?void?add(T?element)?{??
????????//如果链表是空的??
????????if(header?==?null){??
????????????header?=?new?Node(element,?null);??
????????????//只有一个节点，headwe,tail都该指向该节点??
????????????tail?=?header;??
????????}??
????????else{??
????????????Node?newNode?=?new?Node(element,?null);//创建新节点??
????????????tail.next?=?newNode;//尾节点的next指向新节点??
????????????tail?=?newNode;//将新节点作为尾节点??
????????}??
????????size++;??
????}??
????//头部插入??
????public?void?addAtHead(T?element){??
????????//创建新节点，让新节点的next指向header??
????????//并以新节点作为新的header??
????????Node?newNode?=?new?Node(element,?null);??
????????newNode.next?=?header;??
????????header?=?newNode;??
????????//若插入前是空表??
????????if(tail?==?null){??
????????????tail?=?header;??
????????}??
????????size++;??
????}??
????//删除指定索引处的元素??
????public?T?delete(int?index){??
????????if(index?<?0?||?index?>?size-1){??
????????????throw?new?IndexOutOfBoundsException("索引超出线性表范围");??
????????}??
????????Node?del?=?null;??
????????//若要删除的是头节点??
????????if(index?==?0){??
????????????del?=?header;??
????????????header?=?header.next;??
????????}??
????????else{??
????????????Node?prev?=?getNodeByIndex(index?-?1);//获取待删除节点的前一个节点??
????????????del?=?prev.next;//获取待删除节点??
????????????prev.next?=?del.next;??
????????????del.next?=?null;//将被删除节点的next引用置为空??
????????}??
????????size--;??
????????return?del.data;??
????}??
????//删除最后一个元素??
????public?T?remove(){??
????????return?delete(size?-?1);??
????}??
????//判断线性表是否为空??
????public?boolean?isEmpty(){??
????????return?size?==?0;??
????}??
????//清空线性表??
????public?void?clear(){??
????????//将header,tail置为null??
????????header?=?null;??
????????tail?=?null;??
????????size?=?0;??
????}??
????public?String?toString(){??
????????if(isEmpty()){??
????????????return?"[]";??
????????}??
????????else{??
????????????StringBuilder?sb?=?new?StringBuilder("[");??
????????????for(Node?current?=?header;?current?!=?null;?current?=?current.next){??
????????????????sb.append(current.data.toString()?+?",?");??
????????????}??
????????????int?len?=?sb.length();??
????????????return?sb.delete(len-2,?len).append("]").toString();??
????????}??
????}??
}??

四、测试代码

import?org.junit.Test;??
import?com.sihai.algorithm.LinkList;??
public?class?LinkListTest?{??
????@Test??
????public?void?test()?{??
????????//?测试构造函数??
????????LinkList<String>?list?=?new?LinkList("好");??
????????System.out.println(list);??
????????//?测试添加元素??
????????list.add("放大");??
????????list.add("没");??
????????System.out.println(list);??
????????//?在头部添加??
????????list.addAtHead("啦啦啦");??
????????System.out.println(list);??
????????//?在指定位置添加??
????????list.insert("膜拜",?2);??
????????System.out.println(list);??
????????//?获取指定位置处的元素??
????????System.out.println("第2个元素是（从0开始计数）："?+?list.get(2));??
????????//?返回元素索引??
????????System.out.println("膜拜在的位置是："?+?list.locate("膜拜"));??
????????System.out.println("mobai所在的位置："?+?list.locate("mobai"));??
????????//?获取长度??
????????System.out.println("当前线性表的长度："?+?list.length());??
????????//?判断是否为空??
????????System.out.println(list.isEmpty());??
????????//?删除最后一个元素??
????????list.remove();??
????????System.out.println("调用remove()后："?+?list);??
????????//?获取长度??
????????System.out.println("当前线性表的长度："?+?list.length());??
????????//?删除指定位置处元素??
????????list.delete(3);??
????????System.out.println("删除第4个元素后："?+?list);??
????????//?获取长度??
????????System.out.println("当前线性表的长度："?+?list.length());??
????????//?清空??
????????list.clear();??
????????System.out.println(list);??
????????//?判断是否为空??
????????System.out.println(list.isEmpty());??
????}??
}??

五、链表相关的常用操作实现方法

1. 链表反转

/**
?????*?链表反转
?????*?
?????*?@param?head
?????*?@return
?????*/
????public?Node?ReverseIteratively(Node?head)?{
????????Node?pReversedHead?=?head;
????????Node?pNode?=?head;
????????Node?pPrev?=?null;
????????while?(pNode?!=?null)?{
????????????Node?pNext?=?pNode.next;
????????????if?(pNext?==?null)?{
????????????????pReversedHead?=?pNode;
????????????}
????????????pNode.next?=?pPrev;
????????????pPrev?=?pNode;
????????????pNode?=?pNext;
????????}
????????this.head?=?pReversedHead;
????????return?this.head;
????}

2. 查找单链表的中间节点

采用快慢指针的方式查找单链表的中间节点，快指针一次走两步，慢指针一次走一步，当快指针走完时，慢指针刚好到达中间节点。

/**
?????*?查找单链表的中间节点
?????*?
?????*?@param?head
?????*?@return
?????*/
????public?Node?SearchMid(Node?head)?{
????????Node?p?=?this.head,?q?=?this.head;
????????while?(p?!=?null?&&?p.next?!=?null?&&?p.next.next?!=?null)?{
????????????p?=?p.next.next;
????????????q?=?q.next;
????????}
????????System.out.println("Mid:"?+?q.data);
????????return?q;
????}

3. 查找倒数第k个元素

采用两个指针P1,P2，P1先前移K步，然后P1、P2同时移动，当p1移动到尾部时，P2所指位置的元素即倒数第k个元素 。

/**
?????*?查找倒数?第k个元素
?????*?
?????*?@param?head
?????*?@param?k
?????*?@return
?????*/
????public?Node?findElem(Node?head,?int?k)?{
????????if?(k?<?1?||?k?>?this.length())?{
????????????return?null;
????????}
????????Node?p1?=?head;
????????Node?p2?=?head;
????????for?(int?i?=?0;?i?<?k;?i++)//?前移k步
????????????p1?=?p1.next;
????????while?(p1?!=?null)?{
????????????p1?=?p1.next;
????????????p2?=?p2.next;
????????}
????????return?p2;
????}

4. 对链表进行排序

/**
?????*?排序
?????*?
?????*?@return
?????*/
????public?Node?orderList()?{
????????Node?nextNode?=?null;
????????int?tmp?=?0;
????????Node?curNode?=?head;
????????while?(curNode.next?!=?null)?{
????????????nextNode?=?curNode.next;
????????????while?(nextNode?!=?null)?{
????????????????if?(curNode.data?>?nextNode.data)?{
????????????????????tmp?=?curNode.data;
????????????????????curNode.data?=?nextNode.data;
????????????????????nextNode.data?=?tmp;
????????????????}
????????????????nextNode?=?nextNode.next;
????????????}
????????????curNode?=?curNode.next;
????????}
????????return?head;
????}

5. 删除链表中的重复节点

/**
?????*?删除重复节点
?????*/
????public?void?deleteDuplecate(Node?head)?{
????????Node?p?=?head;
????????while?(p?!=?null)?{
????????????Node?q?=?p;
????????????while?(q.next?!=?null)?{
????????????????if?(p.data?==?q.next.data)?{
????????????????????q.next?=?q.next.next;
????????????????}?else
????????????????????q?=?q.next;
????????????}
????????????p?=?p.next;
????????}
????}

6. 从尾到头输出单链表，采用递归方式实现

/**
?????*?从尾到头输出单链表，采用递归方式实现
?????*?
?????*?@param?pListHead
?????*/
????public?void?printListReversely(Node?pListHead)?{
????????if?(pListHead?!=?null)?{
????????????printListReversely(pListHead.next);
????????????System.out.println("printListReversely:"?+?pListHead.data);
????????}
????}

7. 判断链表是否有环，有环情况下找出环的入口节点

/**
?????*?判断链表是否有环，单向链表有环时，尾节点相同
?????*?
?????*?@param?head
?????*?@return
?????*/
????public?boolean?IsLoop(Node?head)?{
????????Node?fast?=?head,?slow?=?head;
????????if?(fast?==?null)?{
????????????return?false;
????????}
????????while?(fast?!=?null?&&?fast.next?!=?null)?{
????????????fast?=?fast.next.next;
????????????slow?=?slow.next;
????????????if?(fast?==?slow)?{
????????????????System.out.println("该链表有环");
????????????????return?true;
????????????}
????????}
????????return?!(fast?==?null?||?fast.next?==?null);
????}
????/**
?????*?找出链表环的入口
?????*?
?????*?@param?head
?????*?@return
?????*/
????public?Node?FindLoopPort(Node?head)?{
????????Node?fast?=?head,?slow?=?head;
????????while?(fast?!=?null?&&?fast.next?!=?null)?{
????????????slow?=?slow.next;
????????????fast?=?fast.next.next;
????????????if?(slow?==?fast)
????????????????break;
????????}
????????if?(fast?==?null?||?fast.next?==?null)
????????????return?null;
????????slow?=?head;
????????while?(slow?!=?fast)?{
????????????slow?=?slow.next;
????????????fast?=?fast.next;
????????}
????????return?slow;
????}

参考资料：

• https://www.cnblogs.com/ganchuanpu/p/7468555.html
• https://blog.csdn.net/jianyuerensheng/article/details/51200274