【数据结构算法(二)】链表总结

简介: 【数据结构算法(二)】链表总结

🌈键盘敲烂,年薪30万🌈



普通单向链表

结点结构:只有val 和 next指针

初始时:head = null;


 

双向链表

指针:prev指针 val next指针

初始时:head = null;


 

带哨兵的链表

初始时:new 一个新节点sentinel val不重要,next = null


 

环形链表

尾节点的next指向头结点

初始时:头结点的next指向自己


 

⭐双向带头带环链表的实现⭐

准备工作

public class TheBestLinkedList implements Iterable<Integer>{
 
    private Node sentinel = new Node(null, 666, null);
 
    public TheBestLinkedList() {
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
    }
    private static class Node{
        Node prev;
        int val;
        Node next;
 
        public Node(Node prev, int val, Node next) {
            this.prev = prev;
            this.val = val;
            this.next = next;
        }
    }
    @Override
    public Iterator<Integer> iterator() {
        return null;
    }
}

addFirst

    public void addFirst(int val){
        Node newNode = new Node(sentinel, val, null);
 
        Node first = sentinel.next;
        newNode.next = first;
        first.prev = newNode;
        sentinel.next = newNode;
    }

addLast

    public void addLast(int val){
        Node newNode = new Node(null, val, sentinel);
        Node last = sentinel.prev;
 
        last.next = newNode;
        newNode.prev = last;
        sentinel.prev = newNode;
 
    }

removedLast

    public Node removedLast(){
        if(isEmpty()){
            return null;
        }
        Node last = sentinel.prev;
        Node removedPrev = last.prev;
 
        sentinel.prev = removedPrev;
        removedPrev.next = sentinel;
        return last;
    }

removedFirst

    public Node removedFirst(){
        if(isEmpty()){
            return null;
        }
        Node first = sentinel.next;
        // 只有一个节点 removedNext = sentinel
        Node removedNext = first.next;
 
        sentinel.next = removedNext;
        removedNext.prev = sentinel;
        return first;
 
    }

isEmpty

    public boolean isEmpty(){
        return sentinel.prev == sentinel;
    }

迭代器遍历

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;
            @Override
            public boolean hasNext() {
                return p != sentinel;
            }
 
            @Override
            public Integer next() {
                int ans =  p.val;
                p = p.next;
                return ans;
            }
        };
    }

 

⭐链表基础OJ⭐

1.反转链表

2.根据值删除链表

3.删除倒数第n个结点

4.有序链表去重

5.合并两个有序链表

6.合并多个有序链表

7.找链表中间结点

8.回文链表

9.链表环问题

相关文章
|
16天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
50 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
19天前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
52 1
|
19天前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
34 0
|
19天前
|
算法
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
【❤️算法笔记❤️】-(每日一刷-876、单链表的中点)
40 0
|
19天前
|
算法
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
29 0
|
19天前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
61 0
|
20小时前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22小时前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
13天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
29 4
|
18天前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)