双（单）向列表分析思路以及代码实现

灰太狼 2024-04-18 23:34 63阅读 0赞

> # **单向链表** #

# **1、链表(Linked List)介绍**** ** #

1)链表是以节点的方式来存储,是链式存储

2)每个节点包含 data 域， next 域：指向下一个节点.

3)如图：发现链表的**各个节点不一定是连续存储**.

4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70][]

![20190914094632409.png][]

# **2、代码实现单向列表crud** #

*  **定义一个节点**

//定义HeroNode ， 每个HeroNode 对象就是一个节点
    class HeroNode {
        public int no;
        public String name;
        public String nickname;
        public HeroNode next; //指向下一个节点
        //构造器
        public HeroNode(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }
        //为了显示方法，我们重新toString
        @Override
        public String toString() {
            return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
        }
    }

*  **单向列表无序添加**
 *     思路，当不考虑编号顺序时
 *     找到当前链表的最后节点  
       将最后这个节点的next 指向 新的节点

private HeroNode head = new HeroNode(0, "", "");
    
    
        //返回头节点
        public HeroNode getHead() {
            return head;
        }
        public void add(HeroNode heroNode) {
    
            //因为head节点不能动，因此我们需要一个辅助遍历 temp
            HeroNode temp = head;
            //遍历链表，找到最后
            while(true) {
                //找到链表的最后
                if(temp.next == null) {//
                    break;
                }
                //如果没有找到最后, 将将temp后移
                temp = temp.next;
            }
            //当退出while循环时，temp就指向了链表的最后
            //将最后这个节点的next 指向 新的节点
            temp.next = heroNode;
        }

**单向列表有序添加**

** **

需要按照编号的顺序添加

1. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定

2. 新的节点.next = temp.next

3. 将temp.next = 新的节点

public void addByOrder(HeroNode heroNode) {
            //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
            //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
            HeroNode temp = head;
            boolean flag = false; // flag标志添加的编号是否存在，默认为false
            while(true) {
                if(temp.next == null) {//说明temp已经在链表的最后
                    break; //
                }
                if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
                    break;
                } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在
    
                    flag = true; //说明编号存在
                    break;
                }
                temp = temp.next; //后移，遍历当前链表
            }
            //判断flag 的值
            if(flag) { //不能添加，说明编号存在
                System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
            } else {
                //插入到链表中, temp的后面
                heroNode.next = temp.next;
                temp.next = heroNode;
            }
        }

**单向列表修改**

根据编号no 来修改，no是不能变的

public void update(HeroNode newHeroNode) {
            //判断是否空
            if(head.next == null) {
                System.out.println("链表为空~");
                return;
            }
            //找到需要修改的节点, 根据no编号
            //定义一个辅助变量
            HeroNode temp = head.next;
            boolean flag = false; //表示是否找到该节点
            while(true) {
                if (temp == null) {
                    break; //已经遍历完链表
                }
                if(temp.no == newHeroNode.no) {
                    //找到
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            //根据flag 判断是否找到要修改的节点
            if(flag) {
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
            } else { //没有找到
                System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
            }
        }

** 删除结点**

从单链表中删除一个节点的思路

1.  我们先找到 需要删除的这个节点的前一个节点 temp

2.  temp.next = temp.next.next

3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

//删除节点
        //思路
        //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
        //2. 说明我们在比较时，是temp.next.no 和  需要删除的节点的no比较
        public void del(int no) {
            HeroNode temp = head;
            boolean flag = false; // 标志是否找到待删除节点的
            while(true) {
                if(temp.next == null) { //已经到链表的最后
                    break;
                }
                if(temp.next.no == no) {
                    //找到的待删除节点的前一个节点temp
                    flag = true;
                    break;
                }
                temp = temp.next; //temp后移，遍历
            }
            //判断flag
            if(flag) { //找到
                //可以删除
                temp.next = temp.next.next;
            }else {
                System.out.printf("要删除的 %d 节点不存在\n", no);
            }
        }

**查询显示列表**

//显示链表[遍历]
        public void list() {
            //判断链表是否为空
            if(head.next == null) {
                System.out.println("链表为空");
                return;
            }
            //因为头节点，不能动，因此我们需要一个辅助变量来遍历
            HeroNode temp = head.next;
            while(true) {
                //判断是否到链表最后
                if(temp == null) {
                    break;
                }
                //输出节点的信息
                System.out.println(temp);
                //将temp后移， 一定小心
                temp = temp.next;
            }
        }

**统计单列表的节点个数**

**如果是头结点, 不需要统计头结点**

/**
         *
         * @param head 链表的头节点
         * @return 返回的就是有效节点的个数
         */
        public static int getLength(HeroNode head) {
            if(head.next == null) { //空链表
                return 0;
            }
            int length = 0;
            //定义一个辅助的变量, 这里我们没有统计头节点
            HeroNode cur = head.next;
            while(cur != null) {
                length++;
                cur = cur.next; //遍历
            }
            return length;
        }
    
    }

**查找链表倒数第K个节点**

**思路：****  实际查询的是 第 size-k 个元素**

1. 编写一个方法，接收head节点，同时接收一个index
    2. index 表示是倒数第index个节点
    3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
    4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
    5. 如果找到了，则返回该节点，否则返回nulll

public static HeroNode findLastIndexNode(HeroNode head, int index) {
            //判断如果链表为空，返回null
            if(head.next == null) {
                return null;//没有找到
            }
            //第一个遍历得到链表的长度(节点个数)
            int size = getLength(head);
            //第二次遍历  size-index 位置，就是我们倒数的第K个节点
            //先做一个index的校验
            if(index <=0 || index > size) {
                return null;
            }
            //定义给辅助变量， for 循环定位到倒数的index
            HeroNode cur = head.next; //3 // 3 - 1 = 2
            for(int i =0; i< size - index; i++) {
                cur = cur.next;
            }
            return cur;
    
        }

**单列表反转**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 1][]

//将单链表反转
        public static void reversetList(HeroNode head) {
            //如果当前链表为空，或者只有一个节点，无需反转，直接返回
            if(head.next == null || head.next.next == null) {
                return ;
            }
    
            //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
            HeroNode cur = head.next;
            HeroNode next = null;// 指向当前节点[cur]的下一个节点
            HeroNode reverseHead = new HeroNode(0, "", "");
            //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
            //动脑筋
            while(cur != null) {
                next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
                cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
                reverseHead.next = cur; //将cur 连接到新的链表上
                cur = next;//让cur后移
            }
            //将head.next 指向 reverseHead.next , 实现单链表的反转
            head.next = reverseHead.next;
        }

**根据栈的特性打印链表**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 2][]

//可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
        public static void reversePrint(HeroNode head) {
            if(head.next == null) {
                return;//空链表，不能打印
            }
            //创建要给一个栈，将各个节点压入栈
            Stack<HeroNode> stack = new Stack<HeroNode>();
            HeroNode cur = head.next;
            //将链表的所有节点压入栈
            while(cur != null) {
                stack.push(cur);
                cur = cur.next; //cur后移，这样就可以压入下一个节点
            }
            //将栈中的节点进行打印,pop 出栈
            while (stack.size() > 0) {
                System.out.println(stack.pop()); //stack的特点是先进后出
            }
        }

> # **双向链表** #

1)单向链表，**查找的方向只能是一个方向**，而双向链表可以向前或者向后查找。

2)单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以**自我删****除**，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).

3) 双向链表分析图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 3][]

**双向列表遍历，修改和单向列表一样（代码实现同上）**

**从双向链表中删除一个节点,  
    说明  
    1 对于双向链表，我们可以直接找到要删除的这个节点  
    2 找到后，自我删除即可**

public void del(int no) {
    
            // 判断当前链表是否为空
            if (head.next == null) {// 空链表
                System.out.println("链表为空，无法删除");
                return;
            }
    
            HeroNode2 temp = head.next; // 辅助变量(指针)
            boolean flag = false; // 标志是否找到待删除节点的
            while (true) {
                if (temp == null) { // 已经到链表的最后
                    break;
                }
                if (temp.no == no) {
                    // 找到的待删除节点的前一个节点temp
                    flag = true;
                    break;
                }
                temp = temp.next; // temp后移，遍历
            }
            // 判断flag
            if (flag) { // 找到
                // 可以删除
                // temp.next = temp.next.next;[单向链表]
                temp.pre.next = temp.next;
                // 这里我们的代码有问题?
                // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
            } else {
                System.out.printf("要删除的 %d 节点不存在\n", no);
            }
        }

** 添加**

// 添加一个节点到双向链表的最后.
        public void add(HeroNode2 heroNode) {
    
            // 因为head节点不能动，因此我们需要一个辅助遍历 temp
            HeroNode2 temp = head;
            // 遍历链表，找到最后
            while (true) {
                // 找到链表的最后
                if (temp.next == null) {//
                    break;
                }
                // 如果没有找到最后, 将将temp后移
                temp = temp.next;
            }
            // 当退出while循环时，temp就指向了链表的最后
            // 形成一个双向链表
            temp.next = heroNode;
            heroNode.pre = temp;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1abb6818222b4142847a3926bbaa230e.png
[20190914094632409.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/90bcae2759be465689ea3a22624edc9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/45c8d82870d148f19031f6b6602d4ee0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8eb5670ca041423787b906d12812e8eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1eXVucWlhbmcxMTE_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/67fb22663ed44d1e974c2d4d13508856.png