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

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

🌈键盘敲烂,年薪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.链表环问题

相关文章
TU^
|
4天前
|
存储 索引
数据结构~~链表
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的
TU^
14 0
|
19小时前
|
存储 Java
Java数据结构:链表
Java数据结构:链表
|
3天前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
7 0
|
3天前
|
算法 C++
c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
|
4天前
|
存储 搜索推荐 算法
C语言数据结构算法,常用10种排序实战
插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 冒泡排序(Bubble Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 基数排序(Radix Sort)
8 1
C语言数据结构算法,常用10种排序实战
|
4天前
|
存储 缓存
数据结构(链表)
数据结构(链表)
10 0
|
5天前
|
算法 测试技术
【数据结构与算法 | 基础篇】单向循环链表实现队列
【数据结构与算法 | 基础篇】单向循环链表实现队列
|
5天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
|
5天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣82
【数据结构与算法 | 基础篇】[链表专题]力扣82
|
5天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234