手写一个LinkedList

实现链表思路

LinkedList和ArrayList使用上基本相同，实际上它们有着截然不同的底层数据结构。ArrayList底层使用的是数组，LinkedList使用的链表。那什么是链表呢，下面我们简单图解一下。

链表顾名思义，就像链子一样环环相扣链接起来，通常我们把链子设计为一个Node类，每一个链子就是一个Node对象，上图是Node对象以及Node对象需要定义的一般属性,下面我们描述下每个属性的作用：

pre属性：保存前面Node对象引用
val属性：保存当前Node的值（可以是个POJO，也可以是包装后的基本数据类型）
next属性：保存后面Node对象引用

下面我们再图解一下的多个链子链接起来的链表是怎么样子的：

在阅读代码前，最好先带着下面这几个问题去阅读：

1、链表初始化应该是怎么样子的

2、新增一个Node需要怎么操作，相对ArrayList来说性能怎么样

3、插入一个Node需要怎么操作，相对ArrayList来说性能怎么样

4、删除一个Node需要怎么操作，相对ArrayList来说性能怎么样

5、获取一个Node需要怎么操作，相对ArrayList来说性能怎么样

实现链表代码

/** * 
 * 数据结构 - 链表 * 
 * * @author laizhiyuan * @since 2019/9/26. */public class LinkedList {
 /** * 链尾 */ private Node footer; /** * 链头 */ private Node header; /** * 大小 */ private int size;
 /** * 添加一个元素,默认追加到最后 * * @param eleVal 元素值 */ public void add(T eleVal) { Node newNode = new Node(); newNode.eleValue = eleVal; if (footer != null) { footer.next = newNode; newNode.pre = footer; } if (header == null) { header = newNode; } footer = newNode; size++; }
 /** * 随机插入元素 * * @param i 下标 * @param eleVal 元素值 */ public void set(int i, T eleVal) {
 this.checkRange(i);
 Node node = this.getNode(i); node.eleValue = eleVal; }
 /** * 随机获取对象 * * @param i 下标 * @return 元素值 */ public T get(int i) {
 //检查是否越界 this.checkRange(i); 

 return this.getNode(i).eleValue; }
 private Node getNode(int i) { //计算中间值 int center = this.size() / 2; //判断是从前往后查找还是从后往前查找 if (i < center) { return this.getNodeFromHeader(i); } else { return this.getNodeFromFooter(i); } }
 /** * 根据下标获取结点对象 从后往前查找 * * @param i 下标 * @return 元素值 */ private Node getNodeFromFooter(int i) {
 //计算倒数数量 int descNum = this.size() - i; Node node = this.footer; //大于1是因为排除上面已经赋值的链尾 while (descNum-- > 1) { //pre:往前 node = node.pre; } return node; }
 /** * 根据下标获取结点对象 从前往后查找 * * @param i 下标 * @return 元素值 */ private Node getNodeFromHeader(int i) { Node node = this.header; //大于1是因为排除上面已经赋值的链头 while (i-- > 1) { //next:往后 node = node.next; } return node; }
 private void checkRange(int index) { if (index >= size || index < 0) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }
 private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + this.size; }
 /** * 根据元素值获取节点对象 * * @param eleVal 元素值 * @return 节点对象 */ private Node get(T eleVal) {
 if (isEmpty()) { throw new IndexOutOfBoundsException(outOfBoundsMsg(1)); }
 Node node = this.header;
 //处理null值 if (eleVal == null) { if (node.eleValue == null) { return node; } while (node.next != null) { node = node.next; if (node.eleValue == null) { return node; } }
 } else { //处理非null值 if (node.eleValue.equals(eleVal)) { return node; } while (node.next != null) { node = node.next; if (node.eleValue.equals(eleVal)) { return node; } } }
 return null; }
 /** * 根据下标删除元素 * * @param i 下标 */ public void remove(int i) { this.checkRange(i); Node node = this.getNode(i); this.removeAfter(node); }
 private void removeAfter(Node node){ if (node != null) { if (node == header){ header = header.next; header.pre = null; }else if (node == footer){ footer = footer.pre; footer.next = null; }else {
 node.pre.next = node.next; node.next.pre = node.pre; } } size--; }
 /** * 删除一个元素值 * * @param eleVal 元素值 */ public void remove(T eleVal) { if (isEmpty()) { throw new IndexOutOfBoundsException(outOfBoundsMsg(1)); } Node node = this.get(eleVal); this.removeAfter(node); }
 /** * 是否为空 * * @return 是 否 */ public boolean isEmpty() { return this.size < 1; }
 /** * 返回链表大小 * * @return 链表大小 */ public int size() { return size; }
 /** * 链表节点类 */ private class Node {
 //链表前一个对象引用 private Node pre; //链表存储的值，支持任意对象 private T eleValue; //链表后一个对象引用 private Node next;
 }

测试链表代码

public static void main(String[] args) {
 LinkedList<string> list = new LinkedList<>();
 System.out.println("插入前size:" + list.size()); System.out.println("插入前isEmpty:" + list.isEmpty());
 list.add("L1"); list.add("L2"); list.add("L3"); list.add("L4"); list.add("L5"); list.add(null);
 System.out.println("插入后size:" + list.size()); System.out.println("插入后isEmpty:" + list.isEmpty());
 for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); }
 System.out.println("第一个元素值为：" + list.get(0)); System.out.println("最后一个元素值为：" + list.get(list.size() - 1));
 System.out.println("修改前index为0的值：" + list.get(0)); list.set(0, "L0"); System.out.println("修改后index为0的值：" + list.get(0));
 System.out.println("获取null为:" + list.get(5));
 System.out.println(list.size()); System.out.println(list.isEmpty());
 list.remove(0); System.out.println("删除后index为0的值：" + list.get(0));
 System.out.println("删除一个元素后的值：" + list.size()); System.out.println(list.isEmpty());
 }
/<string>

测试链表输出

插入前size:0插入前isEmpty:true插入后size:6插入后isEmpty:falseL1L1L2L4L5null第一个元素值为：L1最后一个元素值为：null修改前index为0的值：L1修改后index为0的值：L0获取null为:null6false删除后index为0的值：L2删除一个元素后的值：5false