Java数据结构-2 链表,模拟LinkedList实现

时间:2022-02-26 10:18:32

 链表是我们日常编程中使用频率最高的数据结构之一,它的定义为:

一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点。

 链表也是线性表的一种,与同是线性表的顺序表比起来,却有很大的区别:

  • 顺序表由数组实现,会有存储空间的限制。而链表由一个个存储节点组成,理论上不存在空间限制。
  • 顺序表的元素的访问时间复杂度为O(1),而链表节点的访问时间复杂度为O(n)。
  • 顺序表删除插入节点时间复杂度为O(n),而链表为O(1)。

 关于链表的具体解释,大家可以参考:

链表及相关函数实现

 接下来,以Collection接口中的LinkedList类为模板,为大家介绍双链表的实现。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList是集合类的一种,定义里的继承以及实现关系是集合类要掌握的知识,和我们今天主题不搭边,有兴趣了解集合类的同学可以参考:

Java 集合类

接下来,上代码。

package myLinkedList;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class MyLinkedList<T> implements Iterable<T> {

    /** * 内部属性 */
    // 链表长度
    private int theSize;
    // 链表修改次数,主要用于iterator对象中方法的使用
    private int modCount = 0;
    // 存储链表头节点,方便操作
    private Node<T> head;
    // 存储链表尾节点,同上
    private Node<T> tail;


    /** * 由内部类来存储链表节点数据 */
    private static class Node<T> {
        private T value;
        private Node<T> pre;
        private Node<T> next;

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

    // 无参构造
    public MyLinkedList() {
        // 调用构造方法时,初始化双链表
        doClear();
    }



    /*********************** MyLinkedList 对外显示的方法 ***************************/

    /** * 清空双链表 */
    public void clear() {
        doClear();
    }

    /** * 返回双链表长度 * @return 双链表长度 */
    public int size() {
        return this.theSize;
    }

    /** * 双链表是否为空 * @return true双链表为空, false双链表不为空 */
    public boolean isEmpty() {
        return size() == 0;
    }

    /** * 双链表尾插 * @param x 尾插元素的值 * @return 成功插入 */
    public boolean add(T x) {
        add(size(), x);
        return true;
    }

    /** * 在指定下标处添加元素 * @param index 要插入节点的位置 * @param x 要插入节点的值 * @return 成功插入 */
    public boolean add(int index, T x) {
        addBefore(getNode(index, 0, size()), x);
        return true;
    }

    /** * 取指定下标节点的值 * @param index 下标 * @return 节点的值 */
    public T get(int index) {
        return getNode(index).value;
    }

    /** * 设置指定下标的元素值,并返回旧的值 * @param index 要设置的节点的位置 * @param newValue 设置的值 * @return 返回旧的值 */
    public T set(int index, T newValue) {
        Node<T> node = getNode(index);
        T old = node.value;
        node.value = newValue;
        return old;
    }

    /** * 删除指定下标的元素,并返回删除元素的值 * @param index 要删除的节点的位置 * @return 删除节点的值 */
    public T remove(int index) {
        return remove(getNode(index));
    }

    /*********************** MyLinkedList 内部方法 ***************************/


    /** * 清空双链表 */
    private void doClear() {
        this.head = new Node<>(null, null, null);
        this.tail = new Node<>(null, head, null);
        head.next = tail;

        this.theSize = 0;
        this.modCount++;
    }


    /** * 在指定节点前插入值为x的元素 * @param node 位置 * @param x 插入节点的值 */
    private void addBefore(Node<T> node, T x) {
        Node<T> newNode = new Node<>(x, node.pre, node);
        newNode.pre.next = newNode;
        newNode.next.pre = newNode;
        this.theSize++;
        this.modCount++;
    }

    /** * 删除指定元素 * @param node 要删除的节点 * @return 删除节点的值 */
    private T remove(Node<T> node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;

        this.theSize++;
        this.modCount++;
        return node.value;
    }

    /** * 根据指定下标得到对应的节点 * @param index 下标 * @return 指定下标的节点 */
    private Node<T> getNode(int index) {
        return getNode(index, 0, size()-1);
    }

    /** * 在指定范围内根据下标找到对应节点 * @param index 要查找的节点下标 * @param lower 范围下界 * @param upper 范围上界 * @return 对应下标的节点 */
    private Node<T> getNode(int index, int lower, int upper) {
        Node<T> cur = null;

        if(index<lower || index>upper) {
            throw new IndexOutOfBoundsException();
        }

        // 根据index的大小,分别从头或尾出发,这对于链表的查找来说能够提高效率
        if(index < size()/2) {
            cur = this.head;
            for(int i = 0; i < index; i++) {
                cur = cur.next;
            }
        } else {
            cur = this.tail;
            for(int i = size(); i > index; i--) {
                cur = cur.pre;
            }
        }
        return cur;
    }


    /** * 模拟实现LinkedList类的iterator方法 * @return Iterator的一个对象 */
    @Override
    public Iterator<T> iterator() {
        // 这里我们返回一个继承了 iterator 接口的嵌套类
        return new LinkedListIterator();
    }

    /** * 继承了Iterator接口的实现类 */
    private class LinkedListIterator implements Iterator<T> {

        private Node<T> currentNode = head;
        private int expectedModCount = modCount;
        private boolean canRemove = false;

        @Override
        public boolean hasNext() {
            return currentNode !=  tail;
        }

        @Override
        public T next() {
            if(modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if(!hasNext()) {
                throw new NoSuchElementException();
            }
            T nextValue = currentNode.value;
            currentNode = currentNode.next;
            canRemove = true;
            return nextValue;
        }

        @Override
        public void remove() {
            if(modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if(!canRemove) {
                throw new IllegalStateException();
            }

            MyLinkedList.this.remove(currentNode.pre);
            expectedModCount++;
            canRemove = false;
        }
    }

}

 关于LinkedList模拟实现代码,我已上传至 我的GitHub,欢迎大家指导。