文章目录

(一)链表（Linked List）的简介

(二)链表（Linked List）的设计

(三)动态数组（Dynamic Array）的优化

(四)链表（Linked List）的实现：clear

(五)链表（Linked List）的实现：add

(六)链表（Linked List）的实现：get&set

(七)链表（Linked List）的实现：remove

(八)链表（Linked List）的实现：indexOf

(九)链表（Linked List）的代码汇总&测试

(十)补充

(十一)虚拟头结点

(一)链表（Linked List）的简介

动态数组有个明显的缺点：可能会造成内存空间的大量浪费

能否用到多少就申请多少内存？链表可以办到这一点

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

(二)链表（Linked List）的设计

我们直接把方法都抽取到List父类是没用的，因为ArrayList和LinkedList的实现有所差别（有相同，有不同）

正确的做法是让List成为接口，把方法的声明都放在List接口，由AbstractList去实现这个接口，对于ArrayList和LinkedList的实现都相同的方法可以直接抽取到AbstractList中，然后让ArrayList和LinkedList都继承AbstractList，并且实现抽象方法

List接口代码如下：

问题：为什么static final int ELEMENT_NOT_FOUND = -1;要写在List接口中？

当我们使用多态的写法创建ArrayList时，执行list.indexOf(20)时，如果查询不到，相当于list.indexOf(20) == List.ELEMENT_NOT_FOUND，所以要写在List接口中

其实也可以写在AbstractList抽象类中，但是从设计的角度思考，AbstractList是不可见的，只是起到抽取公共方法的作用，最好不要加在这里

AbstractList抽象类代码如下：

最后让LinkedList继承AbstractList并实现相应方法（方法体先留空），如下：

(三)动态数组（Dynamic Array）的优化

public class ArrayList<E> extends AbstractList<E> {private E[] elements;//所有的元素private static final int DEFAULT_CAPACITY = 10;/*** 指定数组的容量** @param capaticy 容量*/public ArrayList(int capaticy) {capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;elements = (E[]) new Object[capaticy];}/*** 不指定的话默认容量是10*/public ArrayList() {this(DEFAULT_CAPACITY);}/*** 保证要有capacity的容量** @param capacity*/private void ensureCapacity(int capacity) {int oldCapacity = elements.length;if (oldCapacity >= capacity) return;//不需要扩容，直接返回//位运算比浮点运算（oldCapacity * 2）效率高int newCapacity = oldCapacity + (oldCapacity >> 1);//相当于乘1.5（每次扩容1.5倍）E[] newElements = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newElements[i] = elements[i];}elements = newElements;//旧的数组指向新的数组System.out.println(oldCapacity + "扩容为:" + newCapacity);}/*** 清除所有元素*/@Overridepublic void clear() {for (int i = 0; i < size; i++) {elements[i] = null;}size = 0;}/*** 元素的数量** @return*/@Overridepublic int size() {return size;}/*** 是否为空** @return*/@Overridepublic boolean isEmpty() {return size == 0;}/*** 获取index位置的元素** @param index* @return*/@Overridepublic E get(int index) {rangeCheck(index);return elements[index];}/*** 设置index位置的元素** @param index* @param element* @return 原来的元素ֵ*/@Overridepublic E set(int index, E element) {rangeCheck(index);E old = elements[index];elements[index] = element;return old;}/*** 在index位置插入一个元素** @param index* @param element*/@Overridepublic void add(int index, E element) {if (element == null) return;rangeCheckForAdd(index);ensureCapacity(size + 1);//capacity取值为size+1，就是保证比size多一个，不怕不够用for (int i = size; i > index; i--) {elements[i] = elements[i - 1];}elements[index] = element;size++;}/*** 删除index位置的元素** @param index* @return*/@Overridepublic E remove(int index) {rangeCheck(index);E old = elements[index];for (int i = index + 1; i < size; i++) {elements[i - 1] = elements[i];}elements[--size] = null;return old;}/*** 查看元素的索引** @param element* @return*/@Overridepublic int indexOf(E element) {if (element == null) {for (int i = 0; i < size; i++) {if (elements[i] == null) return i;}} else {for (int i = 0; i < size; i++) {if (element.equals(elements[i])) return i;}}return ELEMENT_NOT_FOUND;}@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();//使用StringBuilder拼接字符串效率会更高stringBuilder.append("size=").append(size).append(",[");for (int i = 0; i < size; i++) {if (i != 0) {stringBuilder.append(", ");}stringBuilder.append(elements[i]);}stringBuilder.append("]");return stringBuilder.toString();}}

(四)链表（Linked List）的实现：clear

clear()方法清空所有元素，过程如下：

注意：不需要将next设置为null，因为first=null后，0号元素第一个被销毁，接着是1号元素，直至所有元素被销毁

代码如下：

@Overridepublic void clear() {size = 0;first = null;}

(五)链表（Linked List）的实现：add

add(int index,E element)方法添加元素，过程如下：

现在有一个元素，想添加到1号元素的位置

首先让新元素指向1号元素

然后找到1号元素的前一个元素，让它指向新元素

最后索引发生调整

最后size+1，添加完成

首先要写一个私有方法，private Node<E> node(int index)，实现根据index获取对应的Node，代码如下：

private Node<E> node(int index) {rangeCheck(index);Node<E> node = first;//从first开始，next index次 就可以找到要找的结点for (int i = 0; i < index; i++) {node = node.next;}return node;}

public void add(int index, E element)方法的代码如下：

@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);//要特殊处理index=0的情况if (index == 0) {first = new Node<>(element, first);} else {Node<E> prev = node(index - 1);prev.next = new Node<>(element, prev.next);}size++;}

注意：在编写链表过程中，要注意边界测试，比如index为0、size-1、size时

(六)链表（Linked List）的实现：get&set

借助于刚才写的private Node<E> node(int index)方法可以很简单的实现get()和set()方法，代码如下：

@Overridepublic E get(int index) {return node(index).element;}@Overridepublic E set(int index, E element) {Node<E> node = node(index);E old = node.element;node.element = element;return old;}

注意：get()和set()方法都调用了private Node<E> node(int index)方法，该方法内部已经做了索引的检查，所以无需再检查索引

(七)链表（Linked List）的实现：remove

remove(int index)方法删除元素，过程如下：

比如想要删除index=1的元素

直接让0号元素指向2号元素

此时1号元素就会被销毁了

最后调整元素序号，删除完成

代码如下：

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

(八)链表（Linked List）的实现：indexOf

@Overridepublic int indexOf(E element) {if (element == null) {Node<E> node = first;for (int i = 0; i < size; i++) {if (node.element == null) return i;node = node.next;}} else {Node<E> node = first;for (int i = 0; i < size; i++) {if (element.equals(node.element)) return i;node = node.next;}}return ELEMENT_NOT_FOUND;}

(九)链表（Linked List）的代码汇总&测试

public class LinkedList<E> extends AbstractList<E> {private Node<E> first;private static class Node<E> {E element;Node<E> next;public Node(E element, Node<E> next) {this.element = element;this.next = next;}}@Overridepublic void clear() {size = 0;first = null;}@Overridepublic E get(int index) {return node(index).element;}@Overridepublic E set(int index, E element) {Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);//要特殊处理index=0的情况if (index == 0) {first = new Node<>(element, first);} 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;//从first开始，next index次 就可以找到要找的结点for (int i = 0; i < index; i++) {node = node.next;}return node;}@Overridepublic E remove(int index) {Node<E> node = first;if (index == 0) {first = first.next;} else {Node<E> prev = node(index - 1);node = prev.next;// prev.next = prev.next.next;prev.next = node.next;}size--;return node.element;}@Overridepublic int indexOf(E element) {if (element == null) {Node<E> node = first;for (int i = 0; i < size; i++) {if (node.element == null) return i;node = node.next;}} else {Node<E> node = first;for (int i = 0; i < size; i++) {if (element.equals(node.element)) return i;node = node.next;}}return ELEMENT_NOT_FOUND;}@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();//使用StringBuilder拼接字符串效率会更高stringBuilder.append("size=").append(size).append(",[");Node<E> node = first;for (int i = 0; i < size; i++) {if (i != 0) {stringBuilder.append(", ");}stringBuilder.append(node.element);node = node.next;}stringBuilder.append("]");return stringBuilder.toString();}}

测试如下：

(十)补充

完善remove()方法

修改后如下：

注意：后面的node(int index)虽然会调用rangeCheck(int index)，但是在那之前就有抛出异常的风险，不同于get()和set()方法一开始就调用node(int index)

(十一)虚拟头结点

我们之前的add(int index, E element)和remove(int index)方法都对index=0做了特殊处理，如下：

有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）

首先要增加一个构造函数，如下：

public LinkedList2() {first = new Node<>(null, null);}

然后修改Node<E> node(int index)方法，如下：

修改add(int index, E element)方法，如下：

@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);//当index=0时，会过不了node方法里面的索引判断，所以也要特殊处理Node<E> prev = (index == 0) ? first : node(index - 1);prev.next = new Node<>(element, prev.next);size++;}

修改remove(int index)方法，如下：

@Overridepublic E remove(int index) {rangeCheck(index);Node<E> prev = (index == 0) ? first : node(index - 1);Node<E> node = prev.next;prev.next = node.next;size--;return node.element;}

最后修改toString()方法，如下：