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

小强在此 2024-07-11 16:05:04 阅读 63

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

链表链表的实现链表OJ习题顺序表和链表的区别和联系

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

😀😃😄😄😊😊🙃🙃

在这里插入图片描述

😀😃😄😄😊😊🙃🙃

链表

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

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

单向 双向

带头 不带头

循环 非循环

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

在这里插入图片描述

<code>带头,不带头,如下图所示

在这里插入图片描述

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

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

在这里插入图片描述

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

在这里插入图片描述

链表的实现

<code>// 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.没有增容问题,插入一个开辟一个空间。

在这里插入图片描述



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。