Data Structures (二) - 链表LinkedList实现（Part A）

RiemannHypothesis

发布于 2022-08-19 16:08:48

2370

发布于 2022-08-19 16:08:48

文章被收录于专栏：Elixir

一、引出链表LinkedList

由于数组申请的内存是连续的，当数组的容量非常大时会造成内存空间的浪费，而且一旦容量到达临界点需要重新申请一块更大的内存，如果此时没有连续的内存空间供使用，那么将会造成数据的丢失。而链接是一种链式存储的线性表，所有元素的内存地址不一定是连续的，可以完美解决空间浪费的缺点

0是头节点,3是尾节点

一个链表中肯定至少包含两个成员变量，一个是链表的长度size，另一个是链表的节点Node，而根据图示每个Node节点中肯定又至少包含节点中的元素以及下一个节点Node

二、链表LinkedList实现

创建一个新的Module名为LinkedList，在entity包中新增一个Node实体类

public class Node<T> {

    private T element;
    private Node<T> next;

    public Node(T element, Node<T> next) {
        this.element = element;
        this.next = next;
    }

    public T getElement() {
        return element;
    }

    public void setElement(T element) {
        this.element = element;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

在linked包中定义LinkedList类，链表的接口和动态数组都是线性表，因此他们所包含的接口是一致的，可以定义一个上层接口List,在List接口中定义线性表的接口，接口中只声明，不实现，但是链表和动态数组确实有些接口的实现是相同的，如size()、isEmpty()等，针对这种情况可以再定义一个AbstractList抽象类实现List接口，将一些相同的代码方法在AbstractList中，让LinkedList和ArrayList都继承这个抽象类

List接口

public interface List<T> {

    public static final int ELEMENT_NOT_FOUND = -1;
    
    void clear();

    int size();

    boolean isEmpty();

    boolean contains(T element);

    void add(T element);

    T get(int index);

    T set(int index, T element);

    void add(int index, T element);

    T remove(int index);

    int indexOf(T element);
}

AbstractList 抽象类的定义

public abstract class AbstractList<T> implements List<T> {

    public int size;

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public boolean contains(T element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }


    public void add(T element) {
        add(size, element);
    }

}

clear接口的实现，首先size=0，然后first指向空即可

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

add (int index, T element) - 指定位置添加元素

将55这个节点添加到索引为2的位置上，需要先将要增加的元素将55这个节点添加到索引为2的位置上，然后找到索引2的前一个元素，即索引为1的元素，让索引为1的元素即22指向新增加的元素（1号线），这样新增加的元素的索引就变成2，原来索引为2的元素索引变为3，整个列表长度增加1。新增元素完成。

新增一个方法，获取指定索引位置的元素，链表不是顺序排列的，无法通过list[index]方式快速获取指定索引对应的元素

//获取指定索引对应的元素
public Node getNodeByIndex(int index){
    CheckUtils.checkIndex(index,size);

    Node<T> node = first;
    for (int i = 0; i < index; i++) {
        node = node.getNext();
    }
    return node;
}

get方法就可以通过调用getNodeByIndex方法获取指定索引的Node,在去通过Node调用getElement方法获取该节点的元素

@Override
public T get(int index) {

    return (T) getNodeByIndex(index).getElement();
}

set方法可以先通过获取原来index位置的节点，通过Node的getElement方法获取节点上的元素，在通过Node的setElement方法设置指定的元素到指定索引的节点上

@Override
public T set(int index, T element) {
    Node<T> node = getNodeByIndex(index);
    T oldElement = node.getElement();
    node.setElement(element);
    return oldElement;
}

@Override
public void add(int index, T element) {
    CheckUtils.checkIndex4Add(index,size);
    // 获取指定索引的前一个元素
    Node<T> prevNode = getNodeByIndex(index - 1);
    Node<T> nextNode = getNodeByIndex(index);
    // 创建新的Node
    Node<T> newNode = new Node();
    newNode.setElement(element);
    // 新创建的Node指向下一个元素
    newNode.setNext(nextNode);
    // 指定索引前的元素指向新加入的元素
    prevNode.setNext(newNode);

    size++;
}

remove (int index) - 删除元素

@Override
public T remove(int index) {

    CheckUtils.checkIndex(index,size);

    Node<T> node = first;

    if (index == 0){
        first.next = first.next.next;
    } else {

        Node<T> prev = getNodeByIndex(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size --;
    return node.getElement();
}

重写toString方法

@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("LinkedList {size=").append(size).append(", [");
    Node<T> node = first;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(", ");
        }
        string.append(node.element);
        node = node.next;
    }
    string.append("]}");
    return string.toString();
}

创建LinkedListTest，增加测试方法

public class LinkedListTest {

    List<Integer> linkedList = new LinkedList<>();

    @Before
    public void init() {
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        System.out.println("初始化：" + linkedList);
    }

    @Test
    public void add() {
        linkedList.add(11);
        linkedList.add(34);
        linkedList.add(78);
        linkedList.add(1,99);

        System.out.println("执行add方法后，" + linkedList);
    }

    @Test
    public void remove(){
        linkedList.remove(0);
        System.out.println("执行remove方法删除索引0位置的元素后，" + linkedList);
        linkedList.remove(2);
        System.out.println("再次执行remove方法删除索引2位置的元素后，" + linkedList);
    }

    @Test
    public void indexOf(){
        int i = linkedList.indexOf(3);
        System.out.println("执行indexOf，元素3位置的索引为：" + i);
    }

}

执行LinkedListTest测试类

虚拟头节点

为了统一所有节点的处理逻辑，可以在链表最前面增加一个虚拟的头节点，不存储任何数据

有了虚拟头节点，那么链表中的first就是虚拟头节点，虚拟头节点无论链表是否为空都存在，需要增加一个构造方法

// 增加带有虚拟头节点的构造函数，不管链表中是否存在元素，都有虚拟头节点
public LinkedListWthDummyHead(){
    first = new Node<T>(null,null);
}

//获取指定索引对应的元素
public Node getNodeByIndex(int index){
    CheckUtils.checkIndex(index,size);

    // 从first的next节点开始寻找，虚拟头节点的下一个节点开始
    Node<T> node = first.next;
    for (int i = 0; i < index; i++) {
        node = node.getNext();
    }
    return node;
}

有了虚拟头节点之后，链表中的每一个节点都有前一个节点，没有虚拟头节点时索引为0的节点是没有前一个节点的，所有在获取指定位置的前一个节点时都要进行判断当前节点是否是第一个节点，所以可以对这些代码作统一的修改,无需再判断是否是第一个节点。

修改add方法

@Override
public void add(int index, T element) {

    CheckUtils.checkIndex4Add(index,size);
    
    Node<T> prev = index == 0 ? first : getNodeByIndex(index - 1);
    prev.next = new Node<>(element,prev.next);

    size++;
}

修改remove方法

@Override
public T remove(int index) {
    CheckUtils.checkIndex(index,size);

    Node<T> prev = index == 0 ? first : getNodeByIndex(index - 1);
    Node<T> node = prev.next;
    prev.next = node.next;

    size --;
    return node.element;
}

修改toString()方法

@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("LinkedList {size=").append(size).append(", [");
    Node<T> node = first.next;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(", ");
        }
        string.append(node.element);
        node = node.next;
    }
    string.append("]}");
    return string.toString();
}

创建一个测试类LinkedListWthDummyHeadTest

public class LinkedListWthDummyHeadTest {

    List<Integer> linkedList = new LinkedListWthDummyHead<>();

    @Before
    public void init() {
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        System.out.println("初始化：" + linkedList);
    }

    @Test
    public void add() {
        linkedList.add(11);
        linkedList.add(34);
        linkedList.add(78);
        linkedList.add(1,99);

        System.out.println("执行add方法后，" + linkedList);
    }

    @Test
    public void remove(){
        linkedList.remove(0);
        System.out.println("执行remove方法删除索引0位置的元素后，" + linkedList);
        linkedList.remove(2);
        System.out.println("再次执行remove方法删除索引2位置的元素后，" + linkedList);
    }

    @Test
    public void indexOf(){
        int i = linkedList.indexOf(3);
        System.out.println("执行indexOf，元素3位置的索引为：" + i);
    }
}

执行测试