数据结构の线性结构の链表 | Monster

数据结构の线性结构の链表

链表(Linked List)
  • 链表是有序的列表,但是他在内存中的存储是无序的,链表是以节点的方式来存储,每个节点包含data(保存数据)域和next(指向下一个节点)域,且链表的各个节点不一定是连续存放的,链表分为带头节点的链表和没有头节点的链表,根据实际情况的需求来定
单向链表
  • 单向链表中每个节点存储下一个节点的指针,只允许一个方向的查找,结构如图:

  • 链表并不是按顺序存储的,只是保留了对下一个节点的索引

  • 单链表的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    public class SimpleLinkedListDemo {
    public static void main(String[] args) {
    SimpleLinkedList linkedList = new SimpleLinkedList();
    linkedList.add(new MyNode(2,"Kirito"));
    linkedList.add(new MyNode(1,"Asuna"));
    linkedList.showList();

    SimpleLinkedList linkedList2 = new SimpleLinkedList();
    linkedList2.addBySort(new MyNode(2,"Kirito"));
    linkedList2.addBySort(new MyNode(1,"Asuna"));
    linkedList2.showList();
    linkedList2.modify(new MyNode(2,"Alice"));
    linkedList2.showList();
    linkedList2.addBySort(new MyNode(4,"Naruto"));
    linkedList2.addBySort(new MyNode(3,"Sasukee"));
    linkedList2.showList();
    linkedList2.delete(4);
    linkedList2.showList();

    }
    }





    // 定义单链表
    class SimpleLinkedList{
    // 初始化头结点 指向第一个数据的地址 不存放数据
    private MyNode headerNode = new MyNode(0,"");


    // 添加
    // 找到链表中的最后一个节点 将该节点的next赋予值即可
    // 如果考虑依据某个字段顺序插入到某个位置 需要先找到新添加的节点的位置 然后将其左右两端的节点连接
    public void add(MyNode node){
    // 使用临时变量指向头节点 开始遍历
    MyNode temp = this.headerNode;
    // 开始遍历
    while(true){
    // 如果没有下一个节点 说明已经找到最后一个节点
    if(null == temp.getNextNode()){
    // 跳出循环
    break;
    }

    // 没有找到下一个节点 则将temp的指针后移 继续开始查找
    temp = temp.getNextNode(); //
    }

    // 添加
    temp.setNextNode(node);
    }



    // 添加
    // 找到链表中的最后一个节点 将该节点的next赋予值即可
    // 如果考虑依据某个字段顺序插入到某个位置 需要先找到新添加的节点的位置 然后将其左右两端的节点连接
    public void addBySort(MyNode node){
    // 获取头节点
    MyNode temp = this.headerNode;
    while(true){
    // 已经是最后一个节点
    if(null == temp.getNextNode()){
    break;
    }
    if(temp.getNextNode().getNo() > node.getNo()){ // 找到插入的位置 如果当前节点的下一个节点的编号大于要插入节点 说明当前节点的后一个位置就是要找的位置
    // TODO 已经找到插入的位置
    break;
    }else if(temp.getNextNode().getNo() == node.getNo()){ // 编号一致
    // TODO 重复编号插入
    throw new RuntimeException("该编号已经存在..");
    }
    // 指针后移
    temp = temp.getNextNode();
    }
    // 插入数据
    node.setNextNode(temp.getNextNode()); // 将位置的后一个设置到插入节点之后
    temp.setNextNode(node); // 将插入节点设置到上一个的之后

    }

    // 根据 no修改
    public void modify(MyNode node){
    if(null==this.headerNode){
    // TODO 链表为空
    return;
    }
    MyNode temp = this.headerNode.getNextNode();
    while(true){
    // 已经遍历完成
    if(null == temp){
    break;
    }
    if(temp.getNo() == node.getNo()){
    // TODO 找到对应的节点
    temp.setData(node.getData());
    break;
    }
    temp = temp.getNextNode();
    }
    }

    // 删除节点 找到要删除节点的前一个节点 将其指向它的下个节点的下个节点
    public void delete(int no){
    if(null==this.headerNode){
    // TODO 链表为空
    return;
    }
    MyNode temp = this.headerNode;
    while(true){
    if(null == temp.getNextNode()){
    break;
    }
    if(temp.getNextNode().getNo() == no){
    temp.setNextNode(temp.getNextNode().getNextNode());
    break;
    }
    temp = temp.getNextNode();
    }
    }


    // 显示链表
    public void showList(){
    if(null == this.headerNode){
    // TODO 链表为空
    return;
    }
    MyNode temp = this.headerNode.getNextNode();
    while(true){
    // 链表已经到最后 next为空
    if(null == temp){
    break;
    }
    System.out.println(temp);
    temp = temp.getNextNode();
    }


    }
    }



    // 定义节点
    class MyNode{


    private int no; // 考虑排序的编号

    private String data; // 该节点存放的数据

    private MyNode nextNode; // 指向下一个节点



    public MyNode(int no,String data){
    this.no = no;
    this.data = data;
    }


    @Override
    public String toString() {
    return "Node[no=" + this.no + ",data=" + this.data + "]";
    }

    public String getData() {
    return data;
    }

    public void setData(String data) {
    this.data = data;
    }

    public MyNode getNextNode() {
    return nextNode;
    }

    public void setNextNode(MyNode nextNode) {
    this.nextNode = nextNode;
    }

    public int getNo() {
    return no;
    }

    public void setNo(int no) {
    this.no = no;
    }
    }
  • 扩展

    1. 求单链表中有效节点的个数

      • 只需定义一个后移指针记录即可

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        // 得到单链表的有效元素的个数  不包含头节点
        public int getLength(){
        int length = 0;
        MyNode currentNode = this.headerNode.getNextNode();
        while(currentNode!=null){
        // 如果 当前节点的有下一个节点 length++
        length++;
        currentNode = currentNode.getNextNode(); // 指针后移
        }
        return length;
        }
    2. 获取单链表中倒数第n个节点

      • 倒数第n个节点,即有效节点开始的(总结点数 - n)个节点,迭代对应的次数即可

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        // 获取单链表中倒数第N个数
        public MyNode getLastIndexNode(int index){
        if(this.headerNode.getNextNode() == null){
        return null;
        }
        // 得到有效节点个数
        int length = this.getLength();
        if(index<=0 || index > length){
        // 无效参数
        return null;
        }
        // 遍历 得到节点
        MyNode temp = this.headerNode.getNextNode();
        for(int i = 0; i< length-index;i++){
        temp = temp.getNextNode();
        }

        return temp;
        }
    3. 单链表反转

      • 定义一个新的单链表将链表中的数据依次插入到他的头部 然后将旧的头结点指向新的头结点的下一个节点实现反转,此种方式也被称为头插法

      • 思路图解

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        // 单链表反转
        public void reverseList(){
        MyNode headerNode = this.headerNode; // 头节点
        // 如果当前链表为空 或者长度为1 则无需反转
        if(headerNode.getNextNode()==null || headerNode.getNextNode().getNextNode()==null){
        return;
        }
        // 第一个数据节点
        MyNode currentNode = headerNode.getNextNode();
        MyNode nextNode = null ; // 此变量用于在循环中保留current的下一个节点位置
        MyNode reverseNode = new MyNode(0,""); // 定义新的头节点
        // 遍历 取出每次的节点放置在reverseNode的最前端
        while(currentNode!=null){
        nextNode = currentNode.getNextNode();
        currentNode.setNextNode(reverseNode.getNextNode()); // 先将新链表的数据置于当前节点之后
        reverseNode.setNextNode(currentNode); // 将数据连接到新的链表上实现插入到头部
        currentNode = nextNode; //指针后移
        }
        headerNode.setNextNode(reverseNode.getNextNode()); // 旧的头节点指向新的头结点的下一个节点
        }
    4. 逆序打印单链表(不破坏链表结构)

      • 利用数据结构,将各个节点压入栈中,利用栈的 先进后出 的特点,实现逆序打印

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        public void  printReverse(){
        MyNode currentNode = this.headerNode.getNextNode();
        // 创建栈 将数据压入栈中
        Stack<MyNode> stack = new Stack<>();
        while(currentNode!=null){
        stack.push(currentNode); // 压入栈中
        currentNode = currentNode.getNextNode(); // 指针后移
        }

        while(stack.size()>0){
        System.out.println(stack.pop());
        }
        }
双向链表
  • 单向链表的缺点

    • 单向链表查找的方向只能是一个方向,而双向链表可以向前或者向后查找
    • 单向链表不能自我删除,需要依靠辅助节点,双向链表可以自我删除
  • 双向链表就是在单向链表的基础上,每个节点除了保留下一个节点的指针之外,还保留上一个节点的指针,以此实现向前、向后两个方向的查找

    • 单链表

    • 双向链表

  • 双向链表的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    public class TwoWayLinkedListDemo {
    public static void main(String[] args) {

    MyTwoWayLinkedList linkedList = new MyTwoWayLinkedList();
    linkedList.add(new MyTwoWayNode("Kirito"));
    linkedList.add(new MyTwoWayNode("Asuna"));
    linkedList.add(new MyTwoWayNode("Sakura"));
    linkedList.add(new MyTwoWayNode("Alice"));
    linkedList.add(new MyTwoWayNode("Monster"));
    linkedList.showList();
    System.out.println("---------------------------------");
    linkedList.delete(new MyTwoWayNode("Sakura"));
    linkedList.showList();
    System.out.println("---------------------------------");
    linkedList.delete(new MyTwoWayNode("Alice"));
    linkedList.showList();

    }
    }


    // 双向链表

    //节点
    class MyTwoWayNode {
    private String data;

    private MyTwoWayNode pre; //上一个节点

    private MyTwoWayNode next; // 下一个节点

    public MyTwoWayNode(String data) {
    this.data = data;
    }


    public String getData() {
    return data;
    }

    public void setData(String data) {
    this.data = data;
    }

    public MyTwoWayNode getPre() {
    return pre;
    }

    public void setPre(MyTwoWayNode pre) {
    this.pre = pre;
    }

    public MyTwoWayNode getNext() {
    return next;
    }

    public void setNext(MyTwoWayNode next) {
    this.next = next;
    }

    @Override
    public String toString() {
    return "MyTwoWayNode{" +
    "data='" + data + '\'' +
    '}';
    }
    }


    //双向链表
    class MyTwoWayLinkedList{

    // 头结点
    private MyTwoWayNode headerNode = new MyTwoWayNode("");



    // 遍历双向链表 同单链表基本一致
    public void showList(){
    MyTwoWayNode currentNode = this.headerNode.getNext();
    while(currentNode!=null){
    System.out.println(currentNode);
    currentNode = currentNode.getNext();
    }
    }

    // 添加
    public void add(MyTwoWayNode node){
    if(null==this.headerNode){
    // TODO 链表为空
    return;
    }
    MyTwoWayNode currentNode = this.headerNode;
    while(currentNode.getNext()!=null){
    currentNode = currentNode.getNext(); // 指针后移直到最后一个节点
    }
    currentNode.setNext(node); // 设置原最后一个节点的next指向新的节点
    node.setPre(currentNode); // 新的节点设置pre指向原最后一个节点
    }


    // 删除
    public void delete(MyTwoWayNode node){
    if(null==this.headerNode){
    // TODO 链表为空
    return;
    }
    MyTwoWayNode currentNode = this.headerNode.getNext();
    while(currentNode!=null){
    // 找到要删除的节点
    if(currentNode.getData().equals(node.getData())){
    // 删除 放弃指针 即删除
    currentNode.getPre().setNext(currentNode.getNext());
    if(currentNode.getNext()!=null){ // 要删除的为最后一个节点 则无需设置
    currentNode.getNext().setPre(currentNode.getPre());
    break;
    }
    }
    currentNode = currentNode.getNext();

    }
    }
    }
单向环形链表解决约瑟夫问题
  • 约瑟夫(Josephu)问题

    • 设编号为1,2,… n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人出列,以此类推,直到所有人出列为止,由此产生出一个出队编号的序列

  • 使用单向环形链表可以解决此问题(类似于环形队列)

    • 单向环形链表

  • 单向环形链表初始化节点和遍历的实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    public class JosephuDemo {
    public static void main(String[] args) {
    LoopSimpleLinkedList list = new LoopSimpleLinkedList();
    list.add(5);
    list.show();
    }
    }

    // 单向环形链表
    class LoopSimpleLinkedList{
    private Node firstNode; // 第一个节点

    // 添加 指定个数的节点
    public void add(int nums){
    if(nums<1){
    return;
    }
    firstNode = new Node(1); // 构建第一个节点
    Node currentNode = firstNode;
    for (int i = 2; i<= nums; i++){
    Node node = new Node(i);
    currentNode.setNext(node); // 放置节点最后
    node.setNext(firstNode); // 最后节点指向first构成环
    currentNode = currentNode.getNext(); // 指针后移
    }
    }


    // 遍历环形链表
    public void show(){
    Node currentNode = this.firstNode;
    while(currentNode!=null){
    System.out.println(currentNode);
    if(currentNode.getNext() == this.firstNode) {
    // 当前节点的下一个节点是头结点
    break;
    }
    currentNode = currentNode.getNext();
    }
    }

    }

    // 节点

    class Node {
    private int recId; //编号
    private Node next; // 下一个节点


    public Node(int recId) {
    this.recId = recId;
    }

    public int getRecId() {
    return recId;
    }

    public void setRecId(int recId) {
    this.recId = recId;
    }

    public Node getNext() {
    return next;
    }

    public void setNext(Node next) {
    this.next = next;
    }

    @Override
    public String toString() {
    return "Node{" +
    "recId=" + recId +
    '}';
    }
    }
  • 约瑟夫问题出圈的解决

    • 从开始报数的那个节点开始循环,每走(n-1)步,即将当前节点出圈,直至链表中只剩下一个节点为止

    • 代码实现

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      // 根据编号获取节点
      public Node getNode(int recId){
      Node currentNode = this.firstNode;
      while(currentNode!=null){
      if(currentNode.getRecId()==recId){
      break;
      }
      currentNode = currentNode.getNext();
      }
      return currentNode;
      }


      // 约瑟夫问题 出圈
      /**
      *
      * @param start 从第几个小孩开始报数
      * @param count 数多少下出列
      * @param nums 初始的人数
      */
      public void count(int start,int count,int nums){
      if(start<1 || start> nums){
      // TODO 有误的情况
      return;
      }
      // 获取第一个开始报数的小孩的节点 以及其上一个节点作为头尾指针
      Node first = this.getNode(start);
      int endIndex =(start-1) % nums == 0?nums:(start-1) % nums; // 获取第一个开始报数小孩的上一个节点的位置
      Node end = this.getNode(endIndex);

      // 开始报数 让first和 end 同时移动 (count-1)次,然后出圈 以此类推 直到只剩下一个节点为止
      while(!(first == end)){
      // 移动
      for (int i = 0; i < count -1; i++){
      first = first.getNext();
      end = end.getNext();
      }
      // 此时 first 指向的就是要出圈的小孩
      System.out.printf("出圈:%d\n",first.getRecId());
      // 出圈
      first = first.getNext();
      end.setNext(first);
      }
      System.out.printf("剩余的孤儿%d\n",end.getRecId());
      }
-------------本文结束感谢您的阅读-------------
既然来了就打个赏吧= =
0%