关键词：
线性表是一种十分基础且重要的数据结构，它主要包括以下内容：
- 数组
- 链表
- 队列
- 栈
接下来，我将对这四种数据结构做一个详细的总结，其中对链表实现了十几种常见的操作。希望对你有所帮助。
1.数组
数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
注意点：①.数组是一种线性表；②.连续的内存空间和相同类型的数据
由于第二个性质，数组支持 “随机访问”，根据下表随机访问的时间复杂度为O(1);但与此同时却使得在数组中删除，插入数据需要大量的数据搬移工作。
低效的“插入”和“删除”
插入操作
假如数组的长度为n，我们需要将一个数据插入到数组的第k个位置，我们需要将第k~n位元素都顺序地往后挪动一位。
最好情况时间复杂度为O(1),此时对应着在数组末尾插入元素;
最坏情况时间复杂度为O(n),此时对应着在数组开头插入元素;
平均情况时间复杂度为O(n),因为我们在每个位置插入元素的概率相同，故(1+2+3+……+n)/n=O(n);
但是根据我们的需求，有一个特定的场景。如果数组的数据是有序的，那么我们在插入时就一定要那么做；但是如果数组中存储的数据并没有任何规律，数组只是被当成一个存储数据的集合，我们可以有一个取巧的方法：
直接将第k个元素搬移到数组元素的最后，把新的数据直接放入第k个位置即可（是不是很简单啊），这时插入元素的复杂度为O(1)。
删除操作
和插入操作一样，为了保证内存的连续性，删除操作也需要搬移数据。
最好情况时间复杂度为O(1),此时对应着删除数组末尾的元素;
最坏情况时间复杂度为O(n),此时对应着删除数组开头的元素;
平均情况时间复杂度为O(n),因为我们删除每个位置的元素的概率相同，故(1+2+3+……+n)/n=O(n);
当然，在某些特殊情况下，我们并不一定非要进行复杂的删除操作。我们只是将需要删除的数据记录，并且假装它以经被删除了。直到数组没有更多空间存储数据时，我们再触发一次真正的删除操作即可。
这其实就和生活中的垃圾桶类似，垃圾并没有消失，只是被“标记”成了垃圾，而直到垃圾桶塞满时，才会清理垃圾桶。
警惕数组访问越界
在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。如果疏忽会造成严重的后果。当然，Java会自动检测。
2.链表
- 链表结点表示
- 打印单链表
- 单链表根据索引插入结点
- 获取单链表的长度
- 打印单链表的长度
- 单链表删除指定索引的结点
- 单链表实现元素查找，返回是否存在布尔值
- 单链表删除指定索引的后续节点
- 单链表反转
- 递归地进行单链表反转
- 检测链表中是否含有环
- 删除倒数第k个结点
- 求中间节点
- 有序链表合并
链表结点表示
public class Node
int data;
Node Next;
打印单链表
public class Method
//打印单链表
public static void PrintNode (Node list)
for(Node x=list;x!=null;x=x.Next)
System.out.print(x.data+" ");
System.out.println();
单链表根据索引插入结点
public static Node insert(Node first,int index,Node a)
Node ret = new Node();
ret.Next=first;//创建一个虚拟头节点
Node p=ret;
while((index--)!=0) p=p.Next;
//完成节点的插入操作
a.Next=p.Next;
p.Next=a;
//返回真正的链表头节点地址
return ret.Next;//函数返回链表的头节点
获取单链表的长度
public static int GetLength(Node first)
int n=0;
for(Node x=first;x!=null;x=x.Next)
++n;
return n;
打印单链表的长度
public static void PrintLength(Node first)
System.out.println("Length : "+GetLength(first));
单链表删除指定索引的结点
public static Node Delete(Node first,int index)
if(index<0||index>=GetLength(first)) return first;
else
Node ret=new Node();
ret.Next=first;
Node p=ret;
while((index--)!=0) p=p.Next;
//完成节点的删除操作
p.Next=p.Next.Next;
return ret.Next;
单链表实现元素查找，返回是否存在布尔值
public static boolean Find(Node first,int key)
for(Node x=first;x!=null;x=x.Next)
if(x.data==key) return true;
return false;
单链表删除指定索引的后续节点
public static void RemoveAfter(Node first,int index)
Node ret=new Node();
ret.Next=first;
Node p=ret;
while((index--)!=0) p=p.Next;
p.Next.Next=null;
单链表反转
public static Node reverse(Node list)
Node curr=list,pre=null;
while(curr!=null)
Node next=curr.Next;
curr.Next=pre;
pre=curr;
curr=next;
return pre;
递归地进行单链表反转
public static Node reverseRecursively(Node head)
if(head==null||head.Next==null) return head;//递归的终止条件，返回反转后链表的头节点
Node reversedListHead=reverseRecursively(head.Next);
head.Next.Next=head;//改变这两个结点之间的指向顺序
head.Next=null;
return reversedListHead;//返回反转后的链表头节点
检测链表中是否含有环
public static boolean checkCircle(Node list)
if(list==null) return false;
Node fast=list.Next;
Node slow=list;
while(fast!=null&&fast.Next!=null)
fast=fast.Next.Next;
slow=slow.Next;
if(slow==fast) return true;
return false;
删除倒数第k个结点
public static Node deleteLastKth(Node list,int k)
//利用两个指针，fast和slow，它们之间差k个位置，判断如果fast.Nest=null,也就代表着slow这个位置就是倒数第k个结点
Node fast=list;
int i=1;
while(fast!=null&&i<k)
fast=fast.Next;
++i;
if(fast==null) return list;
Node slow=list;
Node prev=null;
while(fast.Next!=null)
fast=fast.Next;
prev=slow;
slow=slow.Next;
if(prev==null)
list=list.Next;
else
prev.Next=prev.Next.Next;
return list;
求中间节点
public static Node findMiddleNode(Node list)
if(list==null) return null;
Node fast=list;
Node slow=list;
while(fast!=null&&fast.Next!=null)
fast=fast.Next.Next;
slow=slow.Next;
return slow;
有序链表合并
public static Node mergeTwoLists(Node l1,Node l2)
Node soldier=new Node();
Node p=soldier;
while(l1!=null&&l2!=null)
if(l1.data<l2.data)
p.Next=l1;
l1=l2.Next;
else
p.Next=l2;
l2=l2.Next;
p=p.Next;
if(l1!=null) p.Next=l1;
if(l2!=null) p.Next=l2;
return soldier.Next;
3.栈
- 顺序栈
- 链式栈
1.基于数组实现的顺序栈
- 构造函数
- 入栈操作
- 出栈操作
- 打印操作
package Stack;
//基于数组实现的顺序栈
public class ArrayStack
private int[] items;
private int count;//栈中的元素个数
private int n;//栈的大小
//初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n)
this.items=new int[n];
this.n=n;
this.count=0;
//入栈操作
public boolean push(int item)
//数组空间不足，直接返回false，入栈失败
if(count==n) return false;
//将data放在下标为count的位置，并且count加一
items[count]=item;
++count;
return true;
//出栈操作
public int pop()
//栈为空，直接返回-1;
if(count==0) return -1;
//返回下标为count-1的数组元素，并且栈中元素个数count减一
int tmp=items[count-1];
--count;
return tmp;
public void PrintStack()
for(int i=count-1;i>=0;--i)
System.out.print(items[i]+" ");
System.out.println();
2.基于链表的链式栈
- 入栈操作
- 出栈操作
- 打印操作
package Stack;
public class LinkedListStack
private Node top;//栈顶（最近添加的元素）
private int N;//元素数量
private class Node
//定义了结点的嵌套类
int data;
Node Next;
public boolean isEmpty()
return top==null;
public int size()
return N;
public void push(int data)
/*Node newNode=new Node();
//判断是否为空栈
//if(top==null)
newNode=top;
top.data=data;
top.Next=newNode;
N++;*/
Node newNode=top;
top=new Node();
top.data=data;
top.Next=newNode;
++N;
public int pop()
//从栈顶删除元素
if(top==null) return -1;//这里用-1表示栈中没有数据
int data=top.data;
top=top.Next;
N--;
return data;
public void PrintStack()
for(Node x=top;x!=null;x=x.Next)
System.out.print(x.data+" ");
System.out.println();
4.普通队列
- 基于数组实现的普通队列
- 基于链表实现的队列
- 基于数组实现的循环队列
1.基于数组实现的普通队列
- 构造函数
- 入队操作
- 出队操作
- 打印队列中的元素
package Queue;
//用数组实现队列
public class ArrayQueue
//数组：items，数组大小：n
private int[] items;
private int n=0;
//head表示队头下标，tail表示队尾下标
private int head=0;
private int tail=0;
//申请一个大小为capacity的数组
public ArrayQueue(int capacity)
items=new int[capacity];
n=capacity;
//入队(一),基础版
public boolean enqueue(int item)
//如果tail==n，表示队列末尾已经没有空间了
if(tail==n) return false;
items[tail]=item;
++tail;
return true;
//入队（二），改进版
public boolean enqueue1(int item)
//如果tail==n，表示队列末尾已经没有空间了
if(tail==n)
//tail==n&&head==0,表示整个队列都占满了
if(head==0) return false;
//数据搬移
for(int i=head;i<tail;++i)
items[i-head]=items[i];
//搬移完成后重新更新head和tail
tail=tail-head;
head=0;
items[tail]=item;
++tail;
return true;
//出队
public int dequeue()
//如果head==tail，表示队列为空
if(head==tail) return -1;//这里用-1表示队列为空
int ret=items[head];
++head;
return ret;
//打印队列
public void PrintQueue()
for(int i=head;i<tail;++i)
System.out.print(items[i]+" ");
System.out.println();
2.基于链表实现的队列
- 构造函数
- 入队操作
- 出队操作
- 打印队列中的元素
package Queue;
//基于链表实现的队列
public class LinkedListQueue
private Node head;//指向最早添加的结点的链接
private Node tail;//指向最近添加的结点的链接
private int N;//队列中的元素数量
private class Node
//定义了结点的嵌套类
int data;
Node Next;
public boolean isEmpty()
return head==null;
public int size() return N;
//向表尾添加元素,即入队
public void enqueue(int data)
Node newNode=tail;
tail=new Node();
tail.data=data;
tail.Next=null;
if(isEmpty()) head=tail;
else newNode.Next=tail;
++N;
public int dequeue()
//从表头删除元素
int data=head.data;
head=head.Next;
if(isEmpty()) tail=null;
N--;
return data;
//打印输出队列元素
public void PrintQueue()
for(Node x=head;x!=null;x=x.Next)
System.out.print(x.data+" ");
System.out.println();
3.基于数组实现的循环队列
- 构造函数
- 入队操作
- 出队操作
- 打印队列中的元素
package Queue;
public class CircularQueue
//数组items，数组大小n
private int[] items;
private int n=0;
//head表示队头下标，tail表示队尾下标
private int head=0;
private int tail=0;
//申请一个大小为capacity的数组
public CircularQueue(int capacity)
items = new int[capacity];
n=capacity;
//入队
public boolean enqueue(int item)
//队列满了
if((tail+1)%n==head) return false;
items[tail]=item;
tail=(tail+1)%n;//实现计数的循环
return true;
//出队
public int dequeue()
//如果head==tail，表示队列为空
if(head==tail) return -1;//以-1表示队列为空
int ret=items[head];
head=(head+1)%n;
return ret;
//打印队列
public void PrintQueue()
if(n==0) return;
for(int i=head;i%n!=tail;i=(i+1)%n)
System.out.print(items[i]+" ");
System.out.println();
说明
文章代码太多，我本来是希望分成几篇文章写的，但是由于一些原因，最终放在了一起，略显臃肿。代码都是经过测试用例测试过的，应该不会有错误。
如果体验不太好，可以移步我的Github,里面观感较好。
题外话：对于算法初学者，推荐一本十分 nice 的书籍 《算法第四版》，里面各种配图十分详细。如果你需要电子版文件，后台回复算法4即可获得下载链接。后台回复 算法01 送你一份 算法与数据结构思维导图。最后，希望我们一起进步，一起成长！
基础数据结构例：栈队列链表数据字典树等(代码片段)
...tree/B+tree栈stack栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素... 查看详情
链表队列栈(代码片段)
...点由数据元素和下一个节点的存储位置组成，链表结构与数组结构最大区别是链表结构的存储内存是不连续的，而数组结构的内存是连续的，链表结构不能与数组结构一样快速查找?链表机构操作特点是：添加，删除元素效率高... 查看详情
初级--04---链表反转----链表实现栈队列双端队列(代码片段)
...转**Node节点**单链表反转双链表反转单链表实现-----队列线性表--07---队列代码对数器单链表实现-----栈线性表--05---栈代码对数器双端队列代码对数器链表反转Node节点 publicstaticclassNode publicintvalue; publicNodenext; publicNode(intdata) valu... 查看详情
重温四大基础数据结构：数组链表队列和栈(代码片段)
...结构。数组关于数组，大家都比较熟悉了。它是一种线性数据结构，使用一组连续的内存空间存储一组具有相同类型的数据。这个概念中有三个关键 查看详情
3）数据结构之线性表（栈与队列）(代码片段)
目录栈与队列的本质栈的基本概念栈的物理结构栈的顺序存储结构（用数组实现）静态栈的实现： Stack.h中Test/c中Stack.c中输出结果动态栈的实现 Stac.h中Test.c中Stack.c中栈的链式存储结构（使用链表实现） Stack... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议... 查看详情
为什么循环队列要浪费一个存储空间(代码片段)
...什么是队列队列和数组，链表，栈一样都是属于线性数据结构，而队列又和栈比较相似，都属于操作受限的数据结构，其中栈是“后入先出”，而队列是“先进先出”。和栈一样 查看详情
数据结构(c语言版)严蔚敏(线性表队列栈数组树图等数据结构参考代码，持续更新中。。。)(代码片段)
...#xff1a;本篇文章主要提供相关数据结构的实现的参考代码1.线性表线性表的顺序存储（顺序表）和链式存储（链表）1.1顺序表头文件：SqList.h#ifndefSQLIST_H_INCLUDED#defineSQLIST_H_INCLUDED#defineLIST_INIT_SIZE100//顺序表初始大... 查看详情
数据结构——总结
...进行总结，给出一个大概框架。数据结构的主要内容包括线性结构（线性表、栈和队列、串、数组和广义表）、树与二叉树、图、查找以及排序。 线性表是整个数据结构的重要基础，需要熟练掌握顺序表和链表的查找、插入... 查看详情
数组链表队列栈理解
数组一种线性数据结构，使用一组连续的内存空间存储一组具有相同类型的数据。同样是线性结构的还有链表、队列等。它在内存空间中的存储是连续的，不间断的，前后两个元素紧挨着，不存在间隙。通过下标... 查看详情
数据结构与算法—数组栈和链表栈(代码片段)
...的地方，所以才有进栈、出栈的说法。栈是一种受限线性表，也就是说 查看详情
数组和链表的区别arraylist和linkedlist的区别使用linkedlist模拟栈和队列(代码片段)
...1数组和链表的结构的异同相同点：数组和链表都属于线性表，其中数组是属于顺序储存的实现，逻辑存储和物理存储相同而 查看详情
栈与队列(代码片段)
最近一直在看数据结构与算法，下面是对有线性结构的栈与队列的总结：栈相关的内容定义：栈是限定仅在表尾进行插入和删除操作的线性表。（后进先出的线性表）操作：在可以插入与删除的一端称为栈顶，另外一端称为栈底... 查看详情
杨玲徐思《面向对象程序设计（java）》第十一周学习总结(代码片段)
...分：理论知识学习部分1、一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构：线性表、栈、队列、串、数组和文件。非线性数据结构：树和图。2、线性表按其存储结构可分为顺序表和链表；用顺序存... 查看详情
java面试题总结(代码片段)
... 栈：栈是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出(FILO)的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来），... 查看详情
重温四大基础数据结构：数组链表队列和栈(代码片段)
...四大结构。数组关于数组，大家都比较熟悉了。它是一种线性数据结构，使用一组连续的内存空间存储一组具 查看详情
王艳201771010127《面向对象程序设计（java）》第十一周学习总结(代码片段)
一：理论部分。1.数据结构：分为a.线性数据结构，如线性表、栈、队列、串、数组和文件。 b.非线性数据结构，如树和图。1）所有数据元素在同一个线性表中必须是相... 查看详情