手写LinkedList（双向链表）

2020-04-08 本文已影响0人一个多洋

系统jdk里的LinkedList是由一个个节点连接起来的，节点就相当于一个对象，里面有数据域和指针域，数据域是存放数据用的，指针域就是指向下一个节点从而相连接的

这里是一个节点
- 那么链表里是什么样子的呢
- 当有多个节点时，然后它们的前驱和后继都分别指向对方，那么就行成了一个链表

好了，下面我们开撸吧！

我定义了一个泛型类然后在里面定义了一个静态对象里面有2个指针域和一个数据域

public class LinkedList<Y> {...}

2个指针域分别指向它的前面一个节点和后面一个节点（双向链表）

/**
 * 节点
 * LinkedList都是以一个个节点构成的 单向只有一个指针域（指向某位置） 双向则为两个指针域（分别指向前后）
 */
private static class Node<Y> {
    Y item;
    Node<Y> prev;
    Node<Y> next;
    //构造方法
    public Node(Node<Y> prev, Y item, Node<Y> next) {
        this.prev = prev;
        this.item = item;
        this.next = next;
    }
}

然后一个LinkedList集合里肯定会有：头部节点、尾部节点、size（大小）

//头节点
private Node<Y> first;
//尾节点
private Node<Y> last;
//大小
int size = 0;

当想要往里面添加内容时，我这里定义了一个公开方法，然后再把尾部添加方法拿出来，因为后面也会用的到

/**
 * 添加数据到最后
 */
public void add(Y item) {
    linkedLast(item);
}

尾部判断添加方法这里我先new了一个Node对象，然后把他的前驱先指向last，再放入内容，后继先为null，把last单独赋值给l（现在l相当于LinkedList的最后一个值），然后把last赋值为new的Node对象，再判断l是不是null，是的话就把first赋值为new的Node对象，否则把刚才l的后继：next指向new的Node 这样就完成了往最后面添加新节点（对了记得size++）

//往最后面添加数据
private void linkedLast(Y item) {
    Node<Y> newNode = new Node<>(last, item, null);
    //之前的最后一个值
    Node<Y> l = last;
    //把last指向当前插入的值
    last = newNode;
    //里面没有数据
    if (l == null) {
        //当前插入的值就是第一个值
        first = newNode;
    } else {
        //之前的值的后继指向插入的值
        l.next = newNode;
    }
    size++;
}

add()方法完成了那么这里还差add（指定下标，值）方法
这里解释一下：如果插入的下标index是最后一个那么就是直接添加尾部，调用linkedLast(值)方法咯
然后其他原因我的先把当前index的节点Node找出来，方法在再下面，找到了当前index的节点，我就可以把他的pre（前驱）找出来，再根据pre判断，如果为null，就说明当前位置是第一个，把first指向一下，再把刚才用node（index）方法找到的target的前驱指向新节点，这里的target已经相当于新节点的后面一个节点了，不为null就把pre的后继和target的前驱分别指向新节点就ok了（也记得size++）

/**
 * 插入指定位置值
 */
public void add(int index, Y item) {
    //如果输入位置在最后一个
    if (index == size) {
        linkedLast(item);
    } else {
        //当前插入位置的后继
        Node<Y> target = node(index);
        //当前插入位置的前驱
        Node<Y> pre = target.prev;
        //当前准备插的值
        Node<Y> newNode = new Node<>(pre, item, target);
        //pre为null则插入的位置是0 第一个
        if (pre == null) {
            first = newNode;
            //它后面的前驱指定一下
            target.prev = newNode;
        } else {
            //newNode new出来的时候就已经指定了自己的前驱和后继了 现在只要指定它之前的后继和他之后的前驱就行了
            pre.next = newNode;
            target.prev = newNode;
        }
        size++;
    }
}

这里是按下标查找节点，我是先把第一个first赋值为要返回的node，然后根据当前index循环遍历，把node一直指向index位置的节点就行了

//返回指定位置的值
private Node<Y> node(int index) {
    //如果输入下标不符合要求就返回null
    if (index < 0 || index >= size) {
        try {
            throw new Exception("yang say the index is wrong! Do you have any comments?");
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }
    //一遍遍遍历 当前传入第几个就返回当前第几个,可以折中查找 如果index小于一半 就从前往后找
    if (index < size >> 1) {
        Node<Y> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    } else {
        Node<Y> node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
        return node;
    }
}

好了，add(值)和add(指定位置，值)方法都写完了，现在增加还差一个addAll(LinkedList对象)方法如下：
这里很简单，就把传进来的LinkedList集合循环遍历，调用自己的尾部添加方法一个个添加

/**
 * 添加一个linkedList对象进来
 */
public void addAll(LinkedList<Y> linkedList) {
    Y item;
    for (int i = 0; i < linkedList.size; i++) {
        item = linkedList.get(i);
        //一个个添加
        linkedLast(item);
    }
}

增删改查，现在到删了
这边只要把头结点和尾节点分别指向nul，size = 0就行了那么被抛弃的中间那些节点会怎么办呢，别担心，它们会在gc的下一个周期里被回收

/**
 * 删除所有值
 */
public void clear() {
    first = null;
    last = null;
    size = 0;
}

这里是删除指定位置的值我也把方法单独拿出来了

/**
 * 删除某位置值
 */
public void remove(int index) {
    Node<Y> target = node(index);
    unlinkNode(target);
}

根据item删除下面注释很清楚，先分别找出传入item的前驱（pre）和后继（next），然后会有3种情况，下面有介绍，这里我把3种情况分别执行的代码放这里：
1 .当前item是第一个：
    first = item.next; //头结点的后继指向自己的后面一个
    next.prev = item,prev; //下一个的前驱指向自己的前面一个
2 .当前item是中间的：
    pre.next = item.next; //前面的后继指向自己的后继
    next.prev = item.prev; //后面的前驱指向自己的前驱
3 .当前item是最后一个：
    pre.next = item.next; //前面的后继指向自己的后继（null）
    last = item.prev; //尾节点指向自己的前驱

注：其实这里的删除方法和前面讲的gc回收一个道理，当没有指针指向他们的时候他们就会被回收（删除一个数据后记得size--）

//移除某值
private void unlinkNode(Node<Y> item) {
    //分别定义出当前值的前驱和后继
    Node<Y> pre = item.prev;
    Node<Y> next = item.next;
    //删除分3种情况 一种删除的当前值是第一个 一种是中间 一种是最后一个
    //第一个
    if (pre == null) {
        first = item.next;
    } else {
        //让前一个的后继指向自己的后继 然后自己就被跳过了
        pre.next = item.next;
    }
    //最后一个
    if (next == null) {
        last = item.prev;
    } else {
        //让后一个的前驱指向自己的前驱 然后自己就被跳过了（配合上面的一行代码，相当于删除）
        next.prev = item.prev;
    }
    size--;
}

到改了改也是一样的，先根据下标得到当前的节点，然后把节点的item变一下就行了

/**
 * 修改指定位置值
 */
public void update(int index, Y item) {
    Node<Y> node = node(index);
    node.item = item;
}

查根据下标

/**
 * 查询指定位置数据
 */
public Y get(int index) {
    return node(index).item;
}

查根据内容返回下标，重复的话会返回最前面的一个

/**
 * 查询某值的下标
 */
public int find(Y item) {
    Node<Y> node = first;
    for (int i = 0; i < size; i++) {
        if (node.item == item) {
            return i;
        }
        node = node.next;
    }
    return -1;
}

然后我把头节点first和尾节点last私有化了然后提供了一个公开方法获取他们的item

/**
 * 返回第一个
 */
public Y getFirst() {
    return first.item;
}

/**
 * 返回最后一个
 */
public Y getLast() {
    return last.item;
}

好了到这里就完成了自定义LinkedList的简单增删改查
希望不足的地方大家多多指点谢谢大家!

手写LinkedList（双向链表）

好了，下面我们开撸吧！

猜你喜欢

热点阅读