数据结构第三篇【链表的相关知识点一及在线OJ习题】

简介: 数据结构第三篇【链表的相关知识点一及在线OJ习题】

本文章主要讲解关于链表的相关知识,喜欢的可以三连喔

😀😃😄😄😊😊🙃🙃

😀😃😄😄😊😊🙃🙃

链表

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构

单向 双向

带头 不带头

循环 非循环

单链表,双向链表,循环链表如下图所示

带头,不带头,如下图所示

虽然有这么多的链表的结构,但是我们重点掌握两种:

  • 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

  • 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表.

链表的实现

// 1、无头单向非循环链表实现
public class SingleLinkedList {
 //头插法
public void addFirst(int data);
 //尾插法
public void addLast(int data);
 //任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
 //查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
 //删除第一次出现关键字为key的节点
public void remove(int key);
 //删除所有值为key的节点
public void removeAllKey(int key);
 //得到单链表的长度
public int size();
 public void display();
 public void clear();
 }
// 2、无头双向链表实现
public class DoubleLinkedList {
 //头插法
public void addFirst(int data);
 //尾插法
public void addLast(int data);
 //任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
 //查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
 //删除第一次出现关键字为key的节点
public void remove(int key);
 //删除所有值为key的节点
public void removeAllKey(int key);
 //得到单链表的长度
public int size();
 public void display();
 public void clear();
 }

链表OJ习题

大家可以做做习题,感悟链表的精彩

删除链表中等于给定值 val 的所有节点

反转一个单链表

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

输入一个链表,输出该链表中倒数第k个结点。

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

链表的回文结构。

顺序表和链表的区别和联系

顺序表:一白遮百丑 白:空间连续、支持随机访问

丑:1.中间或前面部分的插入删除时间复杂度O(N)

2.增容的代价比较大。

链表:一(胖黑)毁所有

胖黑:以节点为单位存储,不支持随机访问

所有:1.任意位置插入删除时间复杂度为O(1) 2.没有增容问题,插入一个开辟一个空间。

目录
打赏
0
5
7
0
22
分享
相关文章
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
16天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
44 10
|
1月前
|
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
49 10

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等