Java学习笔记（三）- 手写双向链表LinkedList

学习的最好方式就是写出来

欢迎光临我的个人小窝：http://wsfss.top

今天我们就手撸一个简单版的双向链表实现LinkedList吧

1、当然是先写节点类Node

package com.fss.util;

public class Node<E> {

    // 当前节点元素
    E value;

    // 上一个节点
    Node<E> prev;

    // 下一个节点
    Node<E> next;


    public Node(E value, Node<E> next) {
        this.value = value;
        this.next = next;
    }

    public Node(E value, Node<E> prev, Node<E> next) {
        this.value = value;
        this.prev = prev;
        this.next = next;
    }
}

2、实现单向链表的添加元素、下标位置添加元素，移除下标位置元素、获取下标位置元素

package com.fss.util;

import java.util.AbstractSequentialList;
import java.util.ListIterator;
import java.util.NoSuchElementException;

public class LinkedList<T> extends AbstractSequentialList<T> {

    // 链表长度
    transient int size;

    // 头部节点
    transient Node<T> first;

    // 尾部节点
    transient Node<T> last;

    /**
     * 默认在尾部添加
     */
    public boolean add(T t) {
        linkLast(t);
        return true;
    }

    /**
     * 在头部添加
     */
    public boolean addFirst(T t) {
        linkBefore(t);
        return true;
    }

    /**
     * 获取下标位置的节点
     */
    public T get(int index) {
        checkIndex(index);
        Node<T> cur = node(index);
        return cur.value;
    }

    /**
     * 在下标位置添加，下标位置的节点替换为新节点，原下标位置的节点为新节点的下一节点
     * @return
     */
    @Override
    public T set(int index, T t) {
        checkIndex(index);
        size++;
        Node<T> cur = first;
        Node<T> newNode;
        // 头部插入节点
        if (index == 0) {
            newNode = new Node<>(t, cur, cur.next);
            first = newNode;
            newNode.next = cur;
            cur.prev = newNode;
            return t;
        }
        int position = 0;
        while (cur.next != null) {
            if (++position == index) {
                newNode = new Node<>(t, cur, cur.next);
                cur.next = newNode;
            }
            cur = cur.next;
        }
        return t;
    }

    /**
     * 移除下标位置节点，原节点的上一节点的next=原节点的下一节点
     */
    @Override
    public T remove(int index) {
        checkIndex(index);
        Node<T> cur = node(index);
        // 头部节点删除
        if (cur.prev == null) {
            first = cur.next;
        } else {
            cur.prev.next = cur.next;
        }
        size--;
        return cur.value;
    }

    /**
     * 打印链表信息
     */
    public void print() {
        System.out.println("双向链表的长度：" + size);
    }

    /**
     * 获取链表长度
     */
    @Override
    public int size() {
        return this.size;
    }

    @Override
    public ListIterator<T> listIterator(int index) {
        return new ListItr(index);
    }

    /**
     * 在尾部添加节点
     */
    private void linkLast(T t) {
        final Node<T> temp = last;
        // 新节点自动成为尾部节点
        Node<T> newNode = new Node<>(t, temp, null);
        last = newNode;
        // 如果原来的尾部节点为空，表示是第一个节点，此时头部、尾部为同一节点
        if (temp == null) {
            first = newNode;
        } else {
            temp.next = newNode;
        }
        size++;
    }

    /**
     * 在头部添加节点
     */
    private void linkBefore(T t) {
        final Node<T> temp = first;
        Node<T> newNode = new Node<>(t, null, temp);
        first = newNode;
        // 如果原来的头部节点为空，表示是第一个节点，此时头部、尾部为同一节点
        if (temp == null) {
            last = newNode;
        } else {
            temp.prev = newNode;
        }
        size++;
    }

    /**
     * 查找下标位置节点
     */
    private Node<T> node(int index) {
        int half = size >> 1;
        // 下标小于链表长度的一半，从头部开始查找，否则从尾部查找
        Node<T> cur;
        if (index < half) {
            cur = first;
            for (int i=0; i<index; i++) {
                cur = cur.next;
            }
        } else {
            cur = last;
            for (int i=(size -1); i>index; i--) {
                cur = last.prev;
            }
        }
        return cur;
    }

    /**
     * 检查下标是否越界
     */
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超过链表的长度范围");
        }
    }

    /**
     * 重写迭代器，实现单链表结构的迭代
     * 这里只实现了迭代遍历元素，未实现迭代器的add等操作元素的方法
     */
    private class ListItr implements ListIterator<T> {

        // 上一节点
        private Node<T> lastReturned;

        // 下一节点
        private Node<T> next;

        // 下一节点下标
        private int nextIndex;

        public ListItr(int index) {
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        @Override
        public boolean hasNext() {
            return nextIndex < size;
        }

        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.value;
        }

        @Override
        public boolean hasPrevious() {
            return false;
        }

        @Override
        public T previous() {
            if (!hasPrevious())
                throw new NoSuchElementException();
            return null;
        }

        @Override
        public int nextIndex() {
            return nextIndex;
        }

        @Override
        public int previousIndex() {
            return 0;
        }

        @Override
        public void remove() {
        }

        @Override
        public void set(T t) {
        }

        @Override
        public void add(T t) {
        }
    }
}

3、写完了，测试一下

package test;

import com.fss.util.LinkedList;

import java.time.LocalDateTime;

public class LinkedListTest {

    public static void main(String[] args) {
        System.out.println("计时开始：" + LocalDateTime.now());
        LinkedList<Integer> list = new LinkedList<>();
        for (int i=1; i<9; i++) {
            list.add(i);
        }
        System.out.println("计时结束：" + LocalDateTime.now());
        list.print();
        print(list);

        System.out.println("在下标3位置添加元素：" + 0);
        list.set(3, 0);
        print(list);

        System.out.println("移除下标3位置的元素");
        list.remove(3);
        print(list);

        System.out.println("获取下标3位置的元素：" + list.get(3));

    }

    public static void print(LinkedList<Integer> list) {
        for (Object i : list) {
            System.out.print(i);
            System.out.print(",");
        }
        System.out.println();
    }

}

测试结果：

计时开始：2021-12-07T10:40:25.630
计时结束：2021-12-07T10:40:25.633
双向链表的长度：8
1,2,3,4,5,6,7,8,
在下标3位置添加元素：0
1,2,3,0,4,5,6,7,8,
移除下标3位置的元素
1,2,3,4,5,6,7,8,
获取下标3位置的元素：4
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 195,898评论 5赞 462
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 82,401评论 2赞 373
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 143,058评论 0赞 325
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,539评论 1赞 267
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,382评论 5赞 358
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,319评论 1赞 273
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,706评论 3赞 386
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,370评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,664评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,715评论 2赞 312
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,476评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,326评论 3赞 313
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,730评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,003评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,275评论 1赞 251
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,683评论 2赞 342
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,877评论 2赞 335