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

RiemannHypothesis

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

1750

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

文章被收录于专栏：Elixir

一、双向链表DoubleLinkedList

单向链表的缺点是只能单向查询节点，即只能从头节点不断的调用next来获取洗一个节点，如果链表中节点元素非常多，会导致查询效率低下

可以从第一个节点开始调用next往后查询，也可以从尾节点不断调用prev从后往前查询，根据查询的index是在前半段还是后半段进行查询，相比单向链表，可以节省查询时间

修改Node节点实体类，增加prev属性

public class Node<T> {

    public T element;
    public Node<T> next;
    public Node<T> prev;
    // 此处省略有参构造/无参构造/getter/setter方法
}

将linked包中原来的LinkedList复制一份重命名为SingleLinkedList即单向链表，将LinkeListWithDummyHead重命名为SingleLinkedListWithDummyHead，再将LinkedList复制一份重命名为DoubleLinkedList即双向链表，在单向链表的基础上进行双向链表的改造

首先单向链表中除了继承来的属性外还包含了一个头节点，双向链表需要增加一个尾节点的属性

// 第一个Node节点
private Node<T> first;

// 尾节点
private Node<T> last;

第一个要修改的成员方法就是getNodeByIndex(int index)方法，单向链表中查找方式是根据头节点不断的调用getNext()或者next一个一个的查询节点，知道第index个节点，而双向链表可以先判断index是在链表的前半段还是后半段，从而选择从前往后查询还是从后往前查询

//获取指定索引对应的元素
public Node getNodeByIndex(int index){
    CheckUtils.checkIndex(index,size);
    Node<T> node = null;
    if (index < size >> 1){
        node = first;
        for (int i = 0; i < index; i++) {
            node = node.getNext();
        }
    } else {
        node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.getPrev();
        }
    }

    return node;
}

第二个要修改的方法是clear方法，需要将尾节点的指向也改为null

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

第三个要修改的方法是add(int index, T element)，为保证链表不断，现将新加入的节点的prev只想原来index位置节点的prev节点，新加入节点的next指向原index位置的节点

以新加入的节点为参照，下面这三句代码就完成了新节点的next指向原index位置的节点，新节点的prev指向原index-1位置的节点

Node<T> next = getNodeByIndex(index);
Node<T> prev = next.prev;
Node<T> node = new Node<>(element, prev, next);

将原index-1位置节点的next指向新节点，将原来index位置的prev指向新节点

next.prev = node;
prev.next = node;

如果添加到0位置，那么这个节点就是头节点

first=node

如果添加到最后一个，那么这个节点就是尾节点

Node<T> oldLast = last;
last = new Node<T>(element, last, null);
oldLast.next = last;

如果是空链表的情况下，新加入的节点就是第一个节点

fist = last;

add(int index, T element)方法完整代码

@Override
public void add(int index, T element) {
    CheckUtils.checkIndex4Add(index,size);

    if (index == size){
        Node<T> oldLast = last;
        last = new Node<T>(element, last, null);
        if (oldLast == null){
            first = last;
        } else {
            oldLast.next = last;
        }
    } else {
        Node<T> next = getNodeByIndex(index);
        Node<T> prev = next.prev;
        Node<T> node = new Node<>(element, prev, next);

        if (prev == null) {
            first = node;
        } else {
            next.prev = node;
        }
        prev.next = node;
    }
    size++;
}

第四个修改的方法就是remove方法，首先获取index位置的节点以及上一个节点prev以及下一个节点next，删除index位置节点只需要prev的下一个节点指向next，next的上一个节点指向prev，如果删除的是头节点，那么头节点就变为next节点（指定删除节点的下一个节点），如果删除的是尾节点，那么last节点就是prev节点（指定删除节点的上一个节点）

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

    Node<T> node = getNodeByIndex(index);
    Node<T> prev = node.prev;
    Node<T> next = node.next;

    if (prev == null){
        first = next;
    } else {
        prev.next = next;
    }

    if (next == null){
        last = prev;
    } else {
        next.prev = prev;
    }
    size --;
    return node.element;
}

新建一个DoubleLinkedTest测试类，增加测试方法

public class DoubleLinkedListTest {

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

    @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);
    }

}

执行所有方法的测试，控制台输出执行结果

二、单向循环链表

单向循环链表即单向链表的最有一个元素的next指向第一个元素

将linked包中的LinedList复制一份重命名为CircularLinkedList

首先修改add方法

@Override
public void add(int index, T element) {
    CheckUtils.checkIndex4Add(index,size);

    if (index == 0){
        first = new Node<T>(element,first);

        // 拿到最后一个节点,如果size=0就获取第一个节点
        Node<T> last = (size == 0) ? first : getNodeByIndex(size - 1);
        last.next = first;
    } else {
        Node<T> prev = getNodeByIndex(index - 1);
        prev.next = new Node<>(element,prev.next);
    }
    size++;
}

第二个要修改的方法是remove方法

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

    Node<T> node = first;

    if (index == 0){
        if (size == 1){
            first = null;
        } else {
            Node<T> last = getNodeByIndex(size - 1);
            first = first.next;
            last.next = first;
        }
    } else {
        Node<T> prev = getNodeByIndex(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size --;
    return node.element;
}

新建一个测试类，执行这两个方法的测试

public class CircularLinkedListTest {

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

    @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);
    }

}

执行所有方法的测试，控制台输出如下

三、双向循环链表

复制DoubleLinekedList并重命名为DoubleCircularLinkedList，相比双向链表，双向循环链表需要对add方法和remove方法修改

add方法中往最后面添加元素的情况需要修改，双向循环链表往最后添加元素，这个元素的next需要指向first，往第一个位置添加元素的情况也需要修改

@Override
public void add(int index, T element) {
    CheckUtils.checkIndex4Add(index,size);

    if (index == size){
        Node<T> oldLast = last;
        // 最后一个位置插入元素
        last = new Node<T>(element, last, first);
        if (oldLast == null){
            first = last;
            // 只有一个元素的情况下,它的next和prev都指向自己
            first.next = first;
            first.prev = first;
        } else {
            oldLast.next = last;
            first.prev = last;
        }
    } else {
        Node<T> next = getNodeByIndex(index);
        Node<T> prev = next.prev;
        Node<T> node = new Node<>(element, prev, next);

        next.prev = node;
        prev.next = node;

        if (next == first) { // index == 0
            first = node;
        }
    }
    size++;
}

针对remove方法进行修改

@Override
public T remove(int index) {
    CheckUtils.checkIndex(index,size);
    Node<T> node = first;

    if (size == 1){
        first = null;
        last = null;
    } else {
        node = getNodeByIndex(index);
        Node<T> prev = node.prev;
        Node<T> next = node.next;

        prev.next = next;
        prev.prev = prev;

        if (node == first) {
            first = next;
        }

        if (node == last){
            last = prev;
        }
    }
    size --;
    return node.element;
}

增加测试类

public class DoubleCircularLinkedListTest {

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

    @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);
    }


}

执行测试