数据结构之LinkedList&单向链表&双向链表&循环链表

动态数组虽然可以动态改变容量，但却造成了内存空间的浪费。
思考：能不能用多少，就申请多少内存呢？

动态数组：是一种线性存储线性表，内存地址是连续
链表：是一种链式存储的线性表，内存地址不一定是连续的

动态数组和链表继承了AbstractList类，AbstractList实现了List接口。
LinkedList与ArrayList共用同一个接口和同一个抽象类

list接口通用方法

public interface List<E> {
    static final int ELEMENT_NOT_FOUND = -1;
    //清除所有元素
    void clear();
    //元素的数量
    int size();
    //是否为空
    boolean isEmpty();
    //是否包含某个元素
    boolean contains(E element);
    //添加元素到尾部
    void add(E element);
    //获取index位置的元素
    E get(int index);
    //设置index位置的元素
    E set(int index, E element);
    //在index位置插入一个元素
    void add(int index, E element);
    //删除index位置的元素
    E remove(int index);
    //查看元素的索引
    int indexOf(E element);
}

AbstractList抽象类通用方法实现

public abstract class AbstractList<E> implements List<E>  {
    //元素的数量
    protected int size;
    //元素的数量
    public int size() {
        return size;
    }
    //是否为空
    public boolean isEmpty() {
         return size == 0;
    }
    //是否包含某个元素
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }
    //添加元素到尾部
    public void add(E element) {
        add(size, element);
    }
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    protected void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    protected void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
}

singleLinkedList

单向链表说明：

关键变量：

private Node<E> first;
private int size;

first首节点指针，size总节点数量

节点类

private static class Node<E> {
    E element;
    Node<E> next;
    public Node(E element, Node<E> next) {
        this.element = element;
        this.next = next;
    }
}

每个Node节点存放数据值和指针变量，指针变量指向下一个节点

add方法

@Override
public void add(int index, E element) {
    /*
     * 最好：O(1)
     * 最坏：O(n)
     * 平均：O(n)
     */
    rangeCheckForAdd(index);
    
    if (index == 0) {
        first = new Node<>(element, null);
    } else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}

private Node<E> node(int index) {
    rangeCheck(index);
    
    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

添加操作需要修改pre节点的指向和新节点的next指针，当插入如第一个位置时node(index-1)中 index-1 为 -1，不能通过rangeCheck，所以分为头节点和中间及尾部节点添加两种情况进行分析

remove方法

@Override
public E remove(int index) {
    /*
     * 最好：O(1)
     * 最坏：O(n)
     * 平均：O(n)
     */
    rangeCheck(index);

    Node<E> node = first;
    if (index == 0) {
        first = first.next;
    } else {
        Node<E> prev = node(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}

删除和添加一样，注意node(index-1)，依然分为首端和中间及尾部两种情况

增加虚拟头节点

添加和删除都需要单独讨论首端的情况，若增加一个虚拟头节点，则不需要单独讨论

public LinkedList(){
    first=new Node<>(null,null);
}
private Node<E> node(int index){
    rangeCheck(index);
    Node<E> node=first.next;
    for (int i=0;i<size;i++) {
        node=node.next;
    }
    return node;
}
public void add(int index,E element){
    rangeCheckForAdd(index);

    Node<E> pre=index==0?first:node(index-1);
    pre.next=new Node<>(element,pre.next);
    size++;
}
public E remove(int index){
    rangeCheck(index);

    Node<E> pre=index==0?first:node(index-1);
    Node<E> node=pre.next;
    pre.next=node.next;
    size--;
}

indexOf方法

数组与链表的indexOf()逻辑一样，唯一区别是数组采用索引直接取值，链表需要next指针变量提取节点然后取值

优化：

public int indexOf(E element){
    for(int i=0;i<size;i++){
        valEquals(element,node) return i;
    }
    return ELEMENT_NOT_FOUND;
}

public boolean valEquals(E element,Node<E> node){
    return element==null?element==node.element:element.equals(node.element);
}

SingleCircleLinkedList<E>

add方法

单项循环链表的add与单向链表一样，因为Node(0-1)会抛出异常所以分为首端位置插入和尾端位置插入

@Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        
        if (index == 0) {
            Node<E> newFirst = new Node<>(element, first);
            // 拿到最后一个节点
            Node<E> last = (size == 0) ? newFirst : node(size - 1);
            last.next = newFirst;
            first = newFirst;
        } else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

循环链表和单链表区别：
循环链表最后一个节点会指向第一个节点
单链表最后一个节点指向null

remove方法：

@Override
public E remove(int index) {
    rangeCheck(index);
    
    Node<E> node = first;
    if (index == 0) {
        if (size == 1) {
            first = null;
        } else {
            Node<E> last = node(size - 1);
            first = first.next;
            last.next = first;
        }
    } else {
        Node<E> prev = node(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}

对比LinkedList

红框中逻辑相同，都是中间部分的删除
黄框中逻辑不同，循环链表删除第一个节点后，尾端节点next指针指向新的first
因此链表的添加和删除需对端点和中间部分别进行分析

DoubleCircleLinkedList

双向遍历：双向链表可以向前和向后遍历，而单向链表只能沿一个方向遍历。这使得双向链表在某些场景下更加灵活和高效，例如需要在给定节点的前后位置插入或删除节点。队列主要是往头尾操作元素，所以优先使用双向链表。

关键变量：

private Node<E> first;
private Node<E> last;
private int size;

size与之前一样，是节点的总数量，first指向第一个节点，last指向最后一个节点。

add方法：

@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);
    // size == 0
    // index == 0
    if (index == size) { // 往最后面添加元素
        Node<E> oldLast = last;
        last = new Node<>(oldLast, element, first);
        if (oldLast == null) { // 这是链表添加的第一个元素
            first = last;
            first.next = first;
            first.prev = first;
        } else {
            oldLast.next = last;
            first.prev = last;
        }
    } else {
        Node<E> next = node(index); 
        Node<E> prev = next.prev; 
        Node<E> node = new Node<>(prev, element, next);
        next.prev = node;
        prev.next = node;
        
        if (next == first) { // index == 0
            first = node;
        }
    }
    size++;
}

双向链表需要考虑prev的指向，上述代码的执行逻辑：采取条件判断分为最后插入（其中最后插入又需要判断链表的最后元素是否为null,若为null则说明插入的节点是链表第一个节点）和中间插入（中间插入需要重新修改原来前后元素的指向和新建节点的前后指向）

@Override
public E remove(int index) {
    rangeCheck(index);
    return remove(node(index));
}
private E remove(Node<E> node) {
    if (size == 1) {
        first = null;
        last = null;
    } else {
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        prev.next = next;
        next.prev = prev;
        if (node == first) { // index == 0
            first = next;
        }
        if (node == last) { // index == size - 1
            last = prev;
        }
    }
    size--;
    return node.element;
}
public E remove() {
    if (current == null) return null;
    Node<E> next = current.next; 
    E element = remove(current);
    if (size == 0) {
        current = null;
    } else {
        current = next;
    }
    return element;
}

移除索引处节点：删除若链表中只有一个节点，则设置first和last均指向null，断掉依赖即可。else部分，先统一归为中间删除的情况，然后分别考虑删除节点是否是两端节点的情况。
移除当前节点：首先，判断当前节点current是否为null，如果是的话，直接返回null。创建一个临时变量next，用于存储当前节点的下一个节点。调用私有方法remove(current)，将当前节点从链表中移除，并返回被移除节点的元素值。检查链表的大小，如果链表中没有其他节点，将current设置为null。否则，将current更新为next，即移动到下一个节点。最后返回被移除节点的元素值。

双向循环链表中关于reset的使用：

以下是针对CircleLinkedList类中的reset相关方法的使用示例

public class Main {
    public static void main(String[] args) {
        CircleLinkedList<String> list = new CircleLinkedList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");

        // 演示reset()和next()方法
        list.reset(); // 将current重置为第一个节点(A)
        System.out.println("Current element: " + list.next()); // 输出: Current element: B
        System.out.println("Current element: " + list.next()); // 输出: Current element: C

        // 演示remove()方法
        String removedElement = list.remove(); // 移除当前节点(C)
        System.out.println("Removed element: " + removedElement); // 输出: Removed element: C
        System.out.println("Current element: " + list.next()); // 输出: Current element: D

        // 演示clear()方法
        list.clear(); // 清空循环链表
        System.out.println("Size: " + list.size()); // 输出: Size: 0
    }
}

在这个示例中，我们首先创建了一个CircleLinkedList的实例list，并向其中添加了几个元素（A、B、C、D和E）。
然后，我们演示了reset()和next()方法的使用。通过调用reset()方法，我们将current重置为第一个节点（A），然后使用next()方法依次遍历链表中的元素，输出当前节点的元素值。
接下来，我们演示了remove()方法的使用。通过调用remove()方法，我们移除了当前节点（C），并返回了被移除节点的元素值。然后，我们再次调用next()方法，输出当前节点的元素值（D）。
最后，我们演示了clear()方法的使用。通过调用clear()方法，我们清空了循环链表，并使用size()方法验证链表的大小为0。
请注意，以上只是一个使用current相关方法的简单示例，你可以根据需要进行进一步的扩展和逻辑处理。

最后编辑于：2024.03.05 17:06:17

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,607评论 6赞 507
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,239评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,960评论 0赞 355
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,750评论 1赞 294
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,764评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,604评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,347评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,253评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,702评论 1赞 315
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,893评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,015评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,734评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,352评论 3赞 330
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,934评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,052评论 1赞 270
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,216评论 3赞 371
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,969评论 2赞 355

数据结构之LinkedList&单向链表&双向链表&循环链表

list接口通用方法

AbstractList抽象类通用方法实现

singleLinkedList

关键变量：

节点类

add方法

remove方法

indexOf方法

SingleCircleLinkedList<E>

add方法

remove方法：

对比LinkedList

DoubleCircleLinkedList

add方法：

双向循环链表中关于reset的使用：

推荐阅读更多精彩内容