亲宝软件园·资讯

展开

链表的概念、实践和面试题

人气:0

目录
  • 一、链表简介
  • 二、单链表的应用实例
    • 2.1 单链表的基础方法的实现
    • 2.2 单链表的相关面试题

一、链表简介

链表是有序的列表,在内存中的存储方式如图:

  • 链表是以节点的方式来存储,是链式存储;
  • 每个节点包含data域,next指针(指向下一个节点);
  • 链表的节点不一定连续存储,是离散的状态;
  • 链表分为带头节点的链表和没有头结点的链表,带头结点的逻辑结构示意图如下:

二、单链表的应用实例

2.1 单链表的基础方法的实现

使用带头结点的单向链表实现,完成对水浒英雄的CRUD。

  • 普通新增方法
    此方法添加英雄时,直接添加到链表尾部。
  1. 先创建一个head节点,不记录具体信息,作用就是表示单链表的头结点;
  2. 此后每添加一个节点,就直接添加在链表的最后
  3. 示意图:
  • 按序新增方法
    此方法在添加英雄时,根据英雄的排名将英雄添加到指定的位置。
  1. 首先找到新节点应该添加的位置,通过辅助指针来遍历找到位置;
  2. 将新节点的next设置为指针指向节点的next节点;
  3. 将指针指向的节点的next设置新节点;(2、3步骤顺序不能互换)
  4. 不能添加相同排名的英雄;
  5. 示意图:
  • 修改节点方法
  1. 先通过遍历找到对应节点;
  2. 修改数据。
  • 删除节点方法
  1. 找到需要删除的del节点;
  2. 将del节点的前一个节点的next指向del节点的next节点;
  3. 示意图:
  • 代码实现
    GitHub:https://github.com/goSilverhttps://img.qb5200.com/download-x/daydayup/blob/masterhttps://img.qb5200.com/download-x/datastructure/src/hanshunping/chapter04/SingleLinkedListDemo.java

2.2 单链表的相关面试题

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

思路:
遍历单链表,如果有头结点忽略头结点

代码:

    /**
     * 获取链表的长度
     *
     * @param head 链表头结点
     * @return 长度
     */
    int getLength(HeroNode head) {
        int length = 0;
        while (Objects.nonNull(head.getNext())) {
            length++;
            head = head.getNext();
        }
        return length;
    }
  • 查找单链表中的倒数第k个节点
    思路:
  1. 先求得链表的长度length;
  2. 用length - k即可算出倒数第k个节点所处位置;
  3. 从链表头结点遍历length - k次即可。

代码:

    /**
     * 寻找倒数第k个节点
     *
     * @param singleLinkedList 链表
     * @param k                k值
     * @return 倒数第k个节点
     */
    HeroNode findTheKthFromBottom(SingleLinkedList singleLinkedList, int k) {
        int length = getLength(singleLinkedList.head);
        int index = length + 1 - k;
        HeroNode temp = singleLinkedList.head;
        while (Objects.nonNull(singleLinkedList.head.getNext()) && index > 0) {
            temp = temp.getNext();
            index--;
        }
        return temp;
    }
  • 反转链表
  1. 定义一个新的头结点newHead;
  2. 遍历原来的链表,每遍历一个节点,就将这个节点放到newHead的next即可;
  3. 打印时以newHead为头结点打印。

示意图:

代码:

    /**
     * 反转链表
     * 思路:
     * 定义一个新的头结点newHead,遍历链表,依次将遍历的节点取出放到newHead的后面即可
     *
     * @param oldHead 链表的旧头结点
     */
    void reverse(HeroNode oldHead) {
        // 定义一个新的头结点
        HeroNode newHead = new HeroNode(0L, "", "");
        // 定义一个临时节点,记录即将遍历的下一个节点
        HeroNode next;
        // 跳过头节点
        HeroNode current = oldHead.getNext();
        while (Objects.nonNull(current)) {
            // 记录即将遍历的下一个节点
            next = current.getNext();
            // 将newHead的下一个节点设置为当前节点的next
            current.setNext(newHead.getNext());
            // 将newHead的next设置为当前节点
            newHead.setNext(current);
            // 恢复遍历指针
            current = next;
        }
        // 修改链表头结点
        head = newHead;
    }
  • 从尾到头打印单链表
    思路:
    方式1:将单链表先进行反转操作,然后再遍历打印即可,缺点是会破坏原来的单链表的存储结构;
    方式2:可以利用栈数据结构先进后出的特性,从头到尾遍历时将节点依次压入栈中,打印时依次从栈中pop即可。

代码:

    /**
     * 逆向打印链表
     * 思路:
     * 1、先反转链表,再打印链表,缺点是会破坏原链表的结构
     * 2、利用栈数据结构先进后出的特性来辅助实现
     * 这里用栈来实现
     */
    void reversePrint() {
        Stack<HeroNode> nodeStack = new Stack<>();
        HeroNode current = head.getNext();
        while (Objects.nonNull(current)) {
            nodeStack.push(current);
            current = current.getNext();
        }
        while (!nodeStack.isEmpty()) {
            System.out.println(nodeStack.pop());
        }
    }

加载全部内容

相关教程
猜你喜欢
用户评论