• 算法通关村第一关-链表青铜挑战笔记

    欢迎来到 : 第一关青铜关

    1. java如何创建链表
    2. 链表怎么增删改查

    我们先了解链表

    单链表的概念

    我们从简单的创建和增删改查开始.

    链表的概念

    线性表分为顺序表(数组组成)和链表(节点组成) . 

    链表又分: 

    • 单向 双向
    • 有哨兵节点 无哨兵节点
    • 循环 不循环

    链表是一种物理存储单元上非连续、非顺序的存储结构，单链表就像铁链一样,元素之间互相连接。链表由一系列的结点（链表中的每一个元素称为结点也叫节点）组成， 结点可以在运行时动态生成。

     在链表中每个节点都有数据域和指针域两部分:

      数据域用来存值 , 指针域用来存放地址(下一节点的地址) . 

     举个简单的例子{1,2,3}用链表存储:

    思考一下

    思考一下面两个图 , 是否满足单链表的要求 , 为什么 ?

    图一:

    图二:

    解析:

    第一图是满足单链表的要求 , 因为我们说链表要求环环相扣，核心是一个结点只能有一个后继，但不代表个结点只能有一个被指向。第一个图中，c1被a2和b3同时指向，这是没关系的。这就好比法律倡导一夫一妻，你只能爱一个人，但是可以都多个人爱你。
    第二图就不满足要求了，因为c1有两个后继a5和b4.另外在做题的时候要注意比较的是值还是结点，有时可能两个结点的值相等，但并不是同一个结点，例如下图中有两个结点的值都是1，但并不是同一个结点。

    链表的相关概念

    节点和头节点

    每个点都由值和指向下一个结点的地址组成的独立的单元，称为一个结点，有时也称为节点，含义都在链表中，是一样的。
    对于单链表，如果知道了第一个元素，就可以通过遍历访问整个链表，因此第一个结点最重要一般称为头结点

    虚拟节点(哨兵节点)

    在做题以及在工程里经常会看到虚拟结点的概念，其实就是一个结点dummyNode，其next指针指向head，也就是dummyNode.next=head.
    因此，如果我们在算法里使用了虚拟结点，则要注意如果要获得head结点，或者从方法(函数)里返回的时候，则应使用dummyNode.next.
    另外注意，dummyNode的val不会被使用，初始化为0或者-1等都是可以的。既然值不会使用，那虚拟结点有啥用呢?简单来说，就是为了方便我们处理首部结点，否则我们需要在代码里单独处理首部结点的问题。在链表反转里，我们会看到该方式可以大大降低解题难度

    创建链表

    那我们如何使用链表呢？按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个结点存储的元素，用来另外一个属性描述这个结点的下一个结点。

    类名Node
    构造方法Node(T t,Node next)：创建Node对象
    成员变量T value:存储数据 Node next：指向下一个结点

     举例 : 存储值为int类型

    1. /**
    2.  * 节点类
    3.  */
    4. public class Node {
    5.     //值
    6.     int value;
    7.     //地址
    8.     Node next;
    9.  
    10.     public Node(int value, Node next) {
    11.         this.value = value;
    12.         this.next = next;
    13.     }
    14. }

    生成链表：

    1.     public static void main(String[] args) throws Exception {
    2.         //构建结点
    3.         Node first = new Node(11, null);
    4.         Node second = new Node(13, null);
    5.         Node third = new Node(12, null);
    6.         Node fourth = new Node(8, null);
    7.         Node fifth = new Node(9, null);
    8.         //生成链表
    9.         first.next = second;
    10.         second.next = third;
    11.         third.next = fourth;
    12.         fourth.next = fifth;
    13.     }

    添加数据 :

    1.     public static void main(String[] args) throws Exception {
    2.         //构建结点
    3.         Node first = new Node(11, null);
    4.         Node second = new Node(13, null);
    5.         Node third = new Node(12, null);
    6.         Node fourth = new Node(8, null);
    7.         Node fifth = new Node(9, null);
    8.         //生成链表
    9.         first.next = second;
    10.         second.next = third;
    11.         third.next = fourth;
    12.         fourth.next = fifth;
    13.         //添加数据
    14.         Node six= new Node(22, null);
    15.         six.next = second;
    16.         first.next = six;
    17.     }

    删除数据: 

    1.     public static void main(String[] args) throws Exception {
    2.         //构建结点
    3.         Node first = new Node(11, null);
    4.         Node second = new Node(13, null);
    5.         Node third = new Node(12, null);
    6.         Node fourth = new Node(8, null);
    7.         Node fifth = new Node(9, null);
    8.         //生成链表
    9.         first.next = second;
    10.         second.next = third;
    11.         third.next = fourth;
    12.         fourth.next = fifth;
    13.         //添加数据
    14.         Node six= new Node(22, null);
    15.         six.next = second;
    16.         first.next = six;
    17.         //删除数据
    18.         first.next = second;
    19.     }

    修改数据:

    修改值就很简单了找到节点直接修改就可以了:

     first.value = 100;

    单向链表

    单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据， 指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。

    单向链表设计 :

    类名LinkList
    构造方法LinkList()：创建LinkList对象
    成员方法

    1.public void clear()：空置线性表

    2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false

    3.public int length():获取线性表中元素的个数

    4.public T get(int i):读取并返回线性表中的第i个元素的值

    5.public void insert(T t)：往线性表中添加一个元素；

    6.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。

    7.public T remove(int i):删除并返回线性表中第i个数据元素。

    8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则

    返回-11。

    成员内部 类private class Node:结点类
    成员变量

    1.private Node head:记录首结点

    2.private int N:记录链表的长度

    1. /**
    2.  * 单链表 (虚拟节点)
    3.  * @param 
    4.  */
    5. public class LinkList {
    6.     //记录头结点
    7.     private Node head;
    8.     //记录链表的长度
    9.     private int N;
    10.  
    11.     public LinkList() {
    12.         //初始化头结点
    13.         head = new Node(null, null);
    14.         N = 0;
    15.     }
    16.  
    17.     //清空链表
    18.     public void clear() {
    19.         head.next = null;
    20.         head.item = null;
    21.         N = 0;
    22.     }
    23.  
    24.     //获取链表的长度
    25.     public int length() {
    26.         return N;
    27.     }
    28.  
    29.     //判断链表是否为空
    30.     public boolean isEmpty() {
    31.         return N == 0;
    32.     }
    33.  
    34.     //获取指定位置i出的元素
    35.     public T get(int i) {
    36.         if (i < 0 || i >= N) {
    37.             throw new RuntimeException("位置不合法！");
    38.         }
    39.         Node n = head.next;
    40.         for (int index = 0; index < i; index++) {
    41.             n = n.next;
    42.         }
    43.         return n.item;
    44.     }
    45.  
    46.     //向链表中添加元素t
    47.     public void insert(T t) {
    48.         //找到最后一个节点
    49.         Node n = head;
    50.         while (n.next != null) {
    51.             n = n.next;
    52.         }
    53.         Node newNode = new Node(t, null);
    54.         n.next = newNode;
    55.         //链表长度+1
    56.         N++;
    57.     }
    58.  
    59.     //向指定位置i处，添加元素t
    60.     public void insert(int i, T t) {
    61.         if (i < 0 || i >= N) {
    62.             throw new RuntimeException("位置不合法！");
    63.         }
    64.         //寻找位置i之前的结点
    65.         Node pre = head;
    66.         for (int index = 0; index <= i - 1; index++) {
    67.             pre = pre.next;
    68.         }
    69.         //位置i的结点
    70.         Node curr = pre.next;
    71.         Node newNode = new Node(t, curr);
    72.         //让之前的结点指向新结点
    73.         pre.next = newNode;
    74.         //长度+1
    75.         N++;
    76.     }
    77.  
    78.     //删除指定位置i处的元素，并返回被删除的元素
    79.     public T remove(int i) {
    80.         if (i < 0 || i >= N) {
    81.             throw new RuntimeException("位置不合法");
    82.         }
    83.         //寻找i之前的元素
    84.         Node pre = head;
    85.         for (int index = 0; index <= i - 1; index++) {
    86.             pre = pre.next;
    87.         }
    88.         //当前i位置的结点
    89.         Node curr = pre.next;
    90.         //前一个结点指向下一个结点，删除当前结点
    91.         pre.next = curr.next;
    92.         //长度-1
    93.         N--;
    94.         return curr.item;
    95.     }
    96.  
    97.     //查找元素t在链表中第一次出现的位置
    98.     public int indexOf(T t) {
    99.         Node n = head;
    100.         for (int i = 0; n.next != null; i++) {
    101.             n = n.next;
    102.             if (n.item.equals(t)) {
    103.                 return i;
    104.             }
    105.         }
    106.         return -1;
    107.     }
    108.  
    109.     //结点类
    110.     private class Node {
    111.         //存储数据
    112.         T item;
    113.         //下一个结点
    114.         Node next;
    115.  
    116.         public Node(T item, Node next) {
    117.             this.item = item;
    118.             this.next = next;
    119.         }
    120.     }
    121. }

    测试 : 

    1. public class LinkTest {
    2.     public static void main(String[] args) {
    3.         LinkList list = new LinkList<>();
    4.         list.insert("aa");
    5.         list.insert("bb");
    6.         list.insert(1,"cc");
    7.         list.insert("dd");
    8.         for (int i = 0; i < list.length(); i++) {
    9.             System.out.println(list.get(i));
    10.         }
    11.         list.remove(1);
    12.         System.out.println(list.length());
    13.     }
    14. }

    只要设计合理 , 都可以!

    简化一点的版本 : 

    1.  
    2. /**
    3.  * 单向链表
    4.  */
    5. public class SinglyLinkedList {
    6.     //哨兵(头指针)
    7.     private Node head = null;
    8.  
    9.     //节点类
    10.     private static class Node {
    11.         int data;
    12.         Node next;
    13.  
    14.         public Node(int data, Node next) {
    15.             this.data = data;
    16.             this.next = next;
    17.         }
    18.     }
    19.  
    20.     /**
    21.      * 向链表头部插入
    22.      *
    23.      * @param value
    24.      */
    25.     public void addFirst(int value) {
    26.         //1.链表为空的情况
    27.         //head = new Node(value, null);
    28.         //2.链表非空
    29.         head = new Node(value, head);
    30.     }
    31.  
    32.     /**
    33.      * 遍历
    34.      */
    35.     public void foreach(Consumer consumer) {
    36.         Node p = head;
    37.         while (p != null) {
    38.             consumer.accept(p.data);
    39.             p = p.next;
    40.         }
    41.     }
    42.  
    43.     /**
    44.      * 找到最后一个节点
    45.      *
    46.      * @return
    47.      */
    48.     private Node findLast() {
    49.         if (head == null) {
    50.             return null;
    51.         }
    52.         Node p = head;
    53.         while (p.next != null) {
    54.             p = p.next;
    55.         }
    56.         return p;
    57.     }
    58.  
    59.     /**
    60.      * 在链表尾部添加节点
    61.      *
    62.      * @param value
    63.      */
    64.     public void addLast(int value) {
    65.         Node last = findLast();
    66.         if (last == null) {
    67.             addFirst(value);
    68.             return;
    69.         }
    70.         last.next = new Node(value, null);
    71.     }
    72.  
    73.     /**
    74.      * 根据索引查找
    75.      *
    76.      * @param index
    77.      * @return
    78.      */
    79.     private Node findNode(int index) {
    80.         int i = 0;
    81.         for (Node p = head; p != null; p = p.next, i++) {
    82.             if (i == index) {
    83.                 return p;
    84.             }
    85.         }
    86.         return null;
    87.     }
    88.  
    89.     /**
    90.      * 根据索引获取值
    91.      *
    92.      * @param index
    93.      * @return
    94.      */
    95.     public int get(int index) {
    96.         Node node = findNode(index);
    97.         if (node == null) {
    98.             throw new IllegalArgumentException(String.format("index is error"));
    99.         }
    100.         return node.data;
    101.     }
    102.  
    103.  
    104.     /**
    105.      * 向索引位置插入数据
    106.      *
    107.      * @param index
    108.      * @param value
    109.      */
    110.     public void insert(int index, int value) {
    111.         if (index == 0) {
    112.             addFirst(value);
    113.             return;
    114.         }
    115.         Node node = findNode(index - 1);
    116.         if (node == null) {
    117.             throw new IllegalArgumentException(String.format("index is error"));
    118.         }
    119.         node.next = new Node(value, node.next);
    120.     }
    121.  
    122.  
    123.     /**
    124.      * 删除头
    125.      */
    126.     public void removeFirst() {
    127.         if (head == null) {
    128.             throw new IllegalArgumentException("Null");
    129.         } else {
    130.             head = head.next;
    131.         }
    132.     }
    133.  
    134.     /**
    135.      * 按索引删除
    136.      *
    137.      * @param index
    138.      */
    139.     public void removeIndex(int index) {
    140.         if (index == 0) {
    141.             removeFirst();
    142.         } else {
    143.             Node node = findNode(index - 1);
    144.             if (node == null) {
    145.                 throw new IllegalArgumentException("error");
    146.             }
    147.             if (node.next == null) {
    148.                 throw new IllegalArgumentException("error");
    149.             }
    150.             node.next = node.next.next;
    151.         }
    152.     }
    153.  
    154. }

    测试大家自己练习一下......

    双向链表

    双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用 来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存 储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。

     简单写了一下 , 伙伴们自己完善和修改吧 : 

    1.  
    2.  
    3. /**
    4.  * 双链表
    5.  */
    6.  
    7. public class TwoLinkList {
    8.  
    9.     //哨兵节点
    10.     private Node head = new Node(null, -1, null);
    11.  
    12.     //节点
    13.     private static class Node {
    14.         Node pre;
    15.         int value;
    16.         Node next;
    17.  
    18.         public Node(Node pre, int value, Node next) {
    19.             this.pre = pre;
    20.             this.value = value;
    21.             this.next = next;
    22.         }
    23.     }
    24.  
    25.     /**
    26.      * 查找尾节点
    27.      *
    28.      * @return
    29.      */
    30.     private Node findLastNode() {
    31.         Node node = head;
    32.         while (node.next != null ) {
    33.             node = node.next;
    34.         }
    35.         return node;
    36.     }
    37.  
    38.     /**
    39.      * 尾插入
    40.      *
    41.      * @param value
    42.      */
    43.     public void insert(int value) {
    44.         Node lastNode = findLastNode();
    45.         lastNode.next = new Node(lastNode,value,null);
    46.     }
    47.  
    48.     /**
    49.      * 头插入
    50.      *
    51.      * @param value
    52.      */
    53.     public void addFist(int value) {
    54.         //插入
    55.         Node node = head;
    56.         node.next=new Node(head,value,head.next);
    57.     }
    58.  
    59.  
    60.     /**
    61.      * 遍历
    62.      */
    63.     public void forEach() {
    64.         if (head.next == null) {
    65.             System.out.println("null!");
    66.         }else {
    67.             Node p = head.next;
    68.             while (p != null) {
    69.                 System.out.println(p.value);
    70.                 p = p.next;
    71.             }
    72.         }
    73.     }
    74. }

    测试 : 

    1. public class TwoLinkListTest {
    2.     public static void main(String[] args) {
    3.         TwoLinkList twoLinkList = new TwoLinkList();
    4.         twoLinkList.addFist(1);
    5.         twoLinkList.addFist(2);
    6.         twoLinkList.addFist(3);
    7.         twoLinkList.addFist(4);
    8.         twoLinkList.insert(4);
    9.  
    10.         twoLinkList.forEach();
    11.     }
    12. }

    这关就到这里了, 朋友们下一关见!

  • 相关阅读:
    Mysql（Mariadb） 数据库安装在ArchLinux
    创立一年就估值5亿美金，这个项目是怎么做到的？
    SpringBoot整合任务系统（quartz和SpringTask）
    【面试宝典】Java八股文之Redis面试题
    ZigBee环境搭建 -- IAR for 8051 10.30.1
    conda命令大全
    代码自动初始化
    Java学习之TreeSet
    PHP韩语学习网站用wamp、phpstudy运行定制开发mysql数据库BS模式
    PMP每日一练 | 考试不迷路-11.19（包含敏捷+多选）
  • 原文地址：https://blog.csdn.net/sytdsqzr/article/details/133845155