手写LinKedList双向链表终于搞清了什么是链表结构

60 阅读 0 评论 40 点赞

我是靠谱客的博主成就雪碧，最近开发中收集的这篇文章主要介绍手写LinKedList双向链表终于搞清了什么是链表结构，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

之前对Collection这块底层实现和异同点一直模糊不清，最近手动写了个链表结构实现LinKedList ，发现很多知识还是要不断去实践，专研，才能不断提升。

LinKedList 实现 List接口。

链表结构图

a1,a2..都代表每个Node节点。

1：新建一个自定义的节点

package com.kiven.linKedList;
public class Node<E> {
public
E item; //存放数据的泛型
public
Node<E> prev; //上一个节点 这里这个Node 指向自己本身
public
Node<E> next; //下一个节点 这里这个Node 也指向自己本身
public Node() {
super();
}
//有参构造
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

2：新建一个自定义的LinKedList，里面只有三个基本对象，这里一定要有一个思想的转变，这里存对象不像数组，这里是从first这个对象开始往下存，first节点对象的next又存入一个节点对象，以此类推。

MyLinKedList<E>


 public int size = 0;//容量
public Node<E> first;//第一个节点
public Node<E> last;//最后一个节点

3：最基本的方式进行实现。

//实例化我们的myLinKedList
MyLinKedList<String> myLinKedList = new MyLinKedList<>();
//假如我们要把这三个对象放入myLinKedList
String s1="a";
String s2="b";
String s3="c";
//第一次 把s1放入
Node<String> node =new Node<String>(null,s1,null);//第一次存入作为第一个节点，该节点没有上一个 所以第一个参数 null
myLinKedList.first=node;//第一次存入作为第一个节点
myLinKedList.last=node;//第一次存入也作为最后一个节点
myLinKedList.size=1;//容量变为1
Node<String> node2 =new Node<String>(node,s2,null);//第二次存入 ，第一个的node节点就作为第二次的上一个节点。
node.next=node2;//第一个节点的下一个节点
myLinKedList.last=node2;//最后一个节点
myLinKedList.size=2;
Node<String> node3 =new Node<String>(node2,s3,null);//一次类推。
node2.next=node3;
myLinKedList.last=node3;
myLinKedList.size=3;

main方法运行结构图如下：

此时链表的结构就已经出来了，就是一个节点接一个节点。

first a节点下的next对象包含了一个节点b，b节点的next对象包含了一个节点c,以此类推的结构。

写一个get方法：


//get方法 很简单 根据游标 从第一个节点遍历寻找值 这里也可以很清楚的看到为什么链表查询慢
不像arrayList那样查询快
//因为这里是遍历
arrayList是直接根据下标从数组取值，所以arrayList查询要快的多。 
public E get(int index) {
return node(index).item;
}
//这里是源码直接复制过来的
//很巧妙的设计
如果我们查询的这个值排在队伍的后半部分， 从后往前找
。小于后半部分 从前往后找
可以提高效率
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

最后贴上jdk 原版add 方法：

//这里是jdk里的源码
void add(E e) {
final Node<E> l = last;//把最后一个赋予新的对象，第一次是空的
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;//每一次新加入的节点都是最后一个节点
if (l == null) //第一次l是空的
first = newNode;//第一个节点就是新加入的节点
else
l.next = newNode;//否则l的下一个是新加入的节点
这里有点绕，需要一点点调式，是对象的引用改变了first的指定对象
size++;
}

很巧妙地思想，确实编程思想很重要，在我这个层次确实感觉无法写出这样的代码。只有不断去学习，借鉴。