数据结构第三篇【链表的相关知识点一及在线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.没有增容问题，插入一个开辟一个空间。