数据结构与算法(四):双向链表

数据结构与算法 2020-03-12 128 次浏览 本文字数:4178字

本文主要内容:双向链表

双向链表

  1. 单向链表只能通过Node中的next属性(指针)从头遍历链表,完成搜索

  2. 双向链表中的Node增加perv属性,指向该节点的上一个节点

  3. 双向链表查找元素可以从first或last两个方向开始查找

双向链表的接口设计

  1. 相较于单向链表的构造器:需要在构造器中将prev属性放入,同时在初始类时,需要指明一个私有的last节点

  2. 相较于单向链表的方法:需要重写add,remove,node(查找节点),clear四个方法

双向链表结构

双向链表的实现

public class LinkedList<E> {
    private int size;       //用来记录链表长度
    private Node<E> first;  //用来指向初始数据
    private Node<E> last;

    //私有类,用来记录链表中的节点
    private static class Node<E> {
        E element;          //Node类中属性1:用来记录数据
        Node<E> next;       //Node类中属性2:用来记录指针指向下一个元素
        Node<E> prev;       //Node类中属性3:用来记录指针指向前一个元素

        //构造方法
        public Node(Node<E> prev, E element, Node<E> next) {
            this.element = element;
            this.next = next;
            this.prev = prev;
        }
    }

    /**
     * 一、查找元素
     * 通过判断索引在链表的前后判断进行分类
     */
    //通过判断索引在链表的前后判断进行分类
    public Node<E> node(int index) {
        //判断索引是否越界
        rangeCheck(index);

        //在链表前半部分
        if (index < (size >> 1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }else {
            //在链表后半部分
            Node<E> node = last;
            for (int i = size - 1; i > index ; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    /**
     * 二、添加元素
     * 在中间部分插入元素
     *         1. 首先找到索引元素:Node<E> next = node(index);
     *         2. 找到索引元素的前面元素:Node<E> prev = next.prev;
     *         3. 通过Node<E> node = new Node<>(prev, element, next);来实现新元素的prev与next指针的指向
     *         4. 通过prev.next = node;与next.prev = node;来实现原先元素指针的指向
     *     在头部添加元素
     *         见代码实现
     *     在尾部添加元素
     *         见代码实现
     */
    public void add(int index, E element) {
        //检查索引是否越界
        rangeCheckForAdd(index);

        //这是链表添加的第一个元素或者末尾元素
        if (index == size) {
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, null);
            if (oldLast == null) {
                //链表添加的第一个元素
                first = last;
            } else {
                //链表向末尾添加元素
                oldLast.next = last;
            }
        } else {
            //链表向中间添加元素或者向头部添加元素
            Node<E> next = node(index);
            Node<E> prev = next.prev;

            Node<E> node = new Node<>(prev, element, next);
            next.prev = node;
            if (prev == null) {
                //链表向初始添加元素
                first = node;
            } else {
                //链表向中间添加元素
                prev.next = null;
            }
        }
        size++;

    }

    /**
     * 三、删除元素
     * 删除节点:只需让被删节点的前后节点进行连接
     * 同时:需要处理第一个节点和最后一个节点
     */
    public E remove(int index) {
        //检查索引是否越界
        rangeCheck(index);

        // 需要删除的节点
        Node<E> node = node(index);
        // 删除节点的前一个节点
        Node<E> prev = node.prev;
        // 删除节点的后一个节点
        Node<E> next = node.next;
        // 删除节点, 只需要去掉对这个节点的引用即可
        // 如果prev == null, 说明删除的是第一个节点
        if (prev == null) {
            first = next;
        }else {
            prev.next = next;
        }
        // 如果next == null, 说明删除的是最后一个节点
        if (next == null) {
            last = prev;
        }else {
            next.prev = prev;
        }
        size--;
        return node.element;
    }

    /**
     * 四、清空元素
     * 清空元素只需讲first指向null,同时size设为0即可
     */
    public void clear() {
        first = null;
        last = null;
        size = 0;
    }
}

双向链表与动态数组

  1. 动态数组:开辟、销毁内存空间的次数相对较少,但可能造成内存空间浪费(通过缩容解决)
  2. 双向链表:开辟、销毁内存空间的次数相对较多,但不会造成内存空间浪费

  3. 如果频繁在尾部进行添加、删除操作,动态数组与双向链表均可
  4. 如果频繁在头部进行添加、删除操作,建议使用双向链表
  5. 如果有频繁的在任意位置的添加、删除操作,建议使用双向链表
  6. 如果有频繁的查询操作(随机访问操作),建议使用动态数组
  7. 以上操作考虑时间复杂度(最好复杂度,平均复杂度,最好复杂度同时使用)

本文由 WarlockMarten 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。