文章有不当之处，欢迎指正，如果喜欢微信阅读，你也可以关注我的微信公众号：
好好学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实现
下面的程序分别实现了线性表的初始化、获取线性表长度、获取指定索引处元素、根据值查找、插入、删除、清空等操作。
public class LinkList<T> {
// 定义一个内部类Node，代表链表的节点
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 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
相关推荐
这本电子书的内容全部由他本人撰写，实现了严蔚敏版数据结构中90%的算法，包括单链表、排序、广义表、kmp算法、迷宫算法、24点算法、回溯法、二叉树，还写了一些小游戏，有贪吃蛇、俄罗斯方块、迷宫、打字游戏、时钟...
单链表是一种线性数据结构，每个节点包含数据和指向下一个节点的指针。在学生管理系统中，单链表用于存储学生信息，便于进行动态插入、删除和查找操作。链表的头部通常包含指向第一个元素的指针，通过遍历链表，我们...
继承允许一个类（子类）继承另一个类（父类）的属性和方法，从而实现代码复用；多态则指一个接口可以有多种不同的实现，使得程序更具灵活性。 4. **数据结构基础**：数据结构是存储和组织数据的方式，如数组、链表...
【C语言学习笔记VS2015版源码】是一个针对初学者和进阶者设计的教程资源，它特别强调了在Visual Studio 2015环境下进行C语言编程的实际操作和理解。这个教程覆盖了C语言的基础知识，以及一些进阶主题，如数据结构的...
链表不同于数组，它的元素不需要连续的内存空间，每个元素（节点）包含数据和指向下一个节点的指针。单链表、双向链表和循环链表是链表的不同形式，它们在插入、删除操作上具有不同的效率特点。 栈和队列是两种线性...
操作系统课程设计是计算机科学教育中的一个重要环节，它涵盖了操作系统的基本概念、原理以及实现技术。这份压缩包文件包含的资源——"操作系统课程设计 包括实验报告和源代码"，为学习者提供了一次深入理解操作系统...
二叉树是最简单的树形结构，每个节点最多有两个子节点。AVL树和红黑树是自平衡的二叉搜索树，能保证查找、插入和删除操作的平均时间复杂度为O(log n)。 第三章可能会涉及图的概念，图是一种更灵活的数据结构，由...
在阅读和学习提供的完整代码时，务必深入理解每段代码背后的逻辑，并尝试自己动手实现，以便更好地掌握数据结构的精髓。此外，团队合作和代码审查也是提升编程素养的重要环节，可以在交流中发现并改进代码中的问题，...
《C语言数据结构初级》是针对初学者设计的一份学习资料，主要涵盖了C语言基础知识以及数据结构的基本概念和实现。...对于想要从事软件开发或者进一步学习计算机科学的人来说，这是一个很好的起点。
通过这个C语言版的数据结构实现，学习者不仅可以理解数据结构的理论，还能动手实践，从而加深对数据结构的理解，提升编程技能。这是一份宝贵的资源，无论是初学者还是有经验的程序员，都能从中获益匪浅。
C语言是一种广泛用于系统编程和底层应用开发的强大编程语言，因此，《数据结构案例教程(c语言版)》这本书为学习者提供了一个深入理解数据结构并用C语言实现它们的平台。 本书可能涵盖了以下几个重要的数据结构主题...
每个节点包含数据以及指向下一个节点的指针，这使得动态添加和删除元素变得简单。链表分为单链表、双链表和循环链表等类型。 3. **栈**：是一种后进先出（LIFO）的数据结构，常用于实现函数调用、表达式求值等场景...
东南大学网络安全学院的数据结构基础课程设计是一个实践性强、理论与实际相结合的学习项目，旨在帮助学生深入理解数据结构的原理，并通过编程实践提升问题解决能力。 在这个课程设计中，学生可能会接触到以下关键...
3. **链表**：链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表、双链表和循环链表是链表的基本形式，它们在内存中不连续，便于插入和删除操作。 4. **栈与队列**：栈是...
1. **数组**：数组是最基础的数据结构，它是一个元素类型相同的集合，可以通过下标访问每个元素。在C语言中，数组的使用十分常见，如一维数组用于线性数据存储，二维数组则可以模拟表格形式的数据。 2. **链表**：...
3. **文件分配策略**：包括连续分配、链接分配（单链表、双链表、环形链表）、索引分配（直接、一次间接、两次间接等）。每种策略都有其优缺点，需要根据实际需求选择。 4. **磁盘调度算法**：为了高效地访问磁盘，...
《数据结构(C语言版)》演示视频是一套...总之，《数据结构(C语言版)》演示视频结合配套光盘，为学习者提供了一个全面且深入的数据结构学习平台，帮助他们掌握核心概念，提升编程技能，并为未来的软件开发打下坚实基础。
1. **数据结构教程－源程序.rar**：这可能是一个包含C语言实现的各种数据结构（如数组、链表、栈、队列、树、图等）的源代码集合。学习者可以通过阅读和分析这些源代码来深入理解数据结构的内部工作原理，同时也可以...
链表由节点组成，每个节点包含数据和指向下一个节点的指针。单链表、双链表和循环链表是链表的不同形式。C语言中，链表需要手动管理内存，创建和操作链表需要编写更多代码。 3. **栈**：栈是一种后进先出（LIFO）的...