【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)

简介: 【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)


一、链表基本概念和基本代码实现

🍃 动态数组有个明显的缺点:可能会造成内存空间的大量浪费

🍃 能否用到多少就申请多少内存:链表可以办到

🍃 链表是一种链式存储的线性表,所有元素的内存地址不一定连续


🍀 链表(LinkedList)中有 size 属性【记录着链表中元素的个数、节点的个数】

🍀 链表中的 first 被称作头指针【它引用着链表中的第一个节点(头节点)】

🍀 链表中的元素是存储在Node 节点中的,一个Node 节点可被简单看作是一个元素

🍀 Node 也是一个类

🍀 Node 节点中的 element 属性是该 Node 节点 存储的数据

🍀 Node 节点中的 next 属性引用着下一个节点(next 存储着下一个节点的内存地址)

🍀 尾节点的 next 属性不存储任何内容(① 引用着 null;② 指向 null)

public class LinkedList<E> {
    private int size;
    // 头指针
    private Node<E> first;
    /**
     * 每一个节点就是 Node 类的一个实例
     */
    private static class Node<E> {
        E element;
        Node<E> next;
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

二、链表、动态数组整合(面向接口编程)

🧡 ArrayListLinkedList 继承(extends)抽象类 AbstractList

🧡 抽象类 AbstractList 抽取 ArrayList 和 LinkedList 的公共代码,并实现(implements)了 List 接口

🧡 List 接口定义了 LinkedList 和 ArrayList 要实现的全部代码

三、clear()

🧡 没有被引用的对象会被 Java 的垃圾回收器自动回收

public void clear() {
       size = 0;
       first = null;
   }

四、add(int index, E element)

🌼 要往 index 位置插入元素

🌼 找到 index - 1 位置的节点(记作:prev

🌼 让新节点(记作:newNode)的 next 指向 prev.next(是新节点的下一个节点)

🌼 让 prev 的 next 指针指向新节点(记作:newNode

🌼 size++

(1) 找到 index 位置的节点

☃️ 要找 0 号位置的节点【first 头指针指向的就是 0 号位置的节点】

☃️ 要找 1 号位置的节点【first 头指针的 next 指向的就是 1 号位置的节点】

☃️ 要找 2 号位置的节点【first 头指针的 next 的 next 指向的就是 2 号位置的节点】

☃️ 要找0号位置的节点是0次 next,要找1号位置的节点是1次 next,要找2号位置的节点是2次 next,要找 index 位置的节点是 index 次 next

/**
     * 返回 index 位置的节点
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        // 从头节点开始(默认指向头节点)
        Node<E> moveNode = first;
        for (int i = 0; i < index; i++) {
            moveNode = moveNode.next;
        }
        return moveNode;
    }

(2) get(int index) 和 set(int index, E element)

🌴 因为 node() 方法返回了 index 位置的节点,所以 get(int index) 方法(返回 index 位置的元素 ) 方法也得以实现

🌴 因为 node() 方法返回了 index 位置的节点,所以 set(int index, E element) 方法(设置 index 位置的元素为 element ) 方法也得以实现

@Override
    public E get(int index) {
        Node<E> node = node(index);
        return node.element;
    }
@Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        
        node.element = element;
        return old;
    }

(3) add(int index, E element)

🍀 编写链表代码过程中,要注意边界测试

🍀 比如 index 为 0size – 1size

@Override
    public void add(int index, E element) {
        rangeCheck4Add(index);
        if (index == 0) { // 把元素插入到头节点的位置
            first = new Node<>(element, first);
        } else {
            // 拿到【index - 1】位置的节点
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

五、remove(int index)

@Override
    public E remove(int index) {
        rangeCheck(index);
        
        Node<E> node = first;
        if (index == 0) { // 删除头节点
            first = node.next;
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

🌴 注意 index 等于 0 的时候

六、indexOf(E element)

🌴 遍历整个链表,取值比较

@Override
    public int indexOf(E element) {
        Node<E> moveNode = first;
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (null == moveNode.element) return i;
                moveNode = moveNode.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(moveNode.element)) return i;
                moveNode = moveNode.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

七、三个 Leetcode 的练习题

(1) 删除链表中的节点

题目地址:https://leetcode.cn/problems/delete-node-in-a-linked-list/

🌼有一个单链表的 head,我们想删除它其中的一个节点 node

🌼 给你一个需要删除的节点 node

🌼 你无法访问第一个节点 head

🌼 链表的所有值都是唯一的

🌼 给定的节点 node 不是链表中的最后一个节点

🌼 删除节点并不是指从内存中删除它

而是:

① 给定节点的值不应该存在于链表中

② 链表中的节点数应该减少 1

node 前面的所有值顺序相同

node 后面的所有值顺序相同



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

🍃 用要被删除的节点(delNode)的下一个节点的值(delNode.next.val)覆盖 delNode 的值

🍃 delNode 的 next 指向 delNode 的 next 的 next

(2) 反转一个链表

https://leetcode-cn.com/problems/reverse-linked-list/

① 递归反转一个链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

② 迭代反转一个链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}

(3) 判断一个链表是否有环(快慢指针)

https://leetcode.cn/problems/linked-list-cycle/

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

完整代码:https://gitee.com/zgq666good/datastructureandalgorithm.git

如有错误请不吝赐教

相关文章
|
29天前
|
算法 搜索推荐 Java
数据结构与算法(Java篇)笔记--希尔排序
数据结构与算法(Java篇)笔记--希尔排序
|
1月前
|
算法
【数据结构与算法】题解 | #反转链表#
【数据结构与算法】题解 | #反转链表#
|
16天前
|
存储 算法 Java
Java数据结构与算法-java数据结构与算法(二)
Java数据结构与算法-java数据结构与算法
54 1
|
16天前
|
XML 存储 算法
Java数据结构与算法-java数据结构与算法(五)
Java数据结构与算法-java数据结构与算法
47 0
|
18天前
|
存储 机器学习/深度学习 算法
【专题讲解】数据结构与算法——链表(附代码)
【专题讲解】数据结构与算法——链表(附代码)
9 1
|
18天前
|
缓存 安全 Java
Java并发编程中的高效数据结构 - ConcurrentHashMap
本文将深入探讨Java并发编程中的一种高效数据结构 - ConcurrentHashMap。我们将详细介绍ConcurrentHashMap的基本原理,包括其设计思路、实现方式以及如何在多线程环境下提供高效的并发访问。同时,我们还将通过实例代码演示如何使用ConcurrentHashMap来优化并发程序的性能。
|
19天前
|
Java 数据库连接 API
Java 学习路线:基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向对象编程、包、文件和 API
Java 是一种广泛使用的、面向对象的编程语言,始于1995年,以其跨平台性、安全性和可靠性著称,应用于从移动设备到数据中心的各种场景。基础概念包括变量(如局部、实例和静态变量)、数据类型(原始和非原始)、条件语句(if、else、switch等)、函数、循环、异常处理、数据结构(如数组、链表)和面向对象编程(类、接口、继承等)。深入学习还包括包、内存管理、集合框架、序列化、网络套接字、泛型、流、JVM、垃圾回收和线程。构建工具如Gradle、Maven和Ant简化了开发流程,Web框架如Spring和Spring Boot支持Web应用开发。ORM工具如JPA、Hibernate处理对象与数
85 3
|
28天前
|
存储 Java
Java链表
Java链表
10 0
|
29天前
|
算法 搜索推荐 Java
数据结构与算法(Java篇)笔记--快速排序
数据结构与算法(Java篇)笔记--快速排序
|
29天前
|
机器学习/深度学习 算法 搜索推荐
数据结构与算法(Java篇)笔记--归并排序
数据结构与算法(Java篇)笔记--归并排序