【数据结构】双向链表——Java实现一个简单的双向链表

前言

昨天写完单向链表和栈结构之后，看了看程杰大大的书中有介绍双向链表的部分。虽然是c语言写的，但是我还是用Java给翻译出来了。思路如下： 首先，双向链表和单向链表的最大区别就是，双向链表比单链表多了个指向前一节点的指针。代码量其实并不比单链表多很多，只是思路的转变需要克服一下。 其次就是在插入元素的时候，我们可以在链表的头部插入，也可以在链表的尾部插入（因为有两个指针嘛）

编码

代码其实和单链表差不多，如果感兴趣的话可以去看看我之前写的单链表的文章。虽然文笔很烂，但是代码货真价实。

package com.zxy.lianbiao;

/**
 * @Author Zxy
 * @Date 2021/2/4 20:11
 * @Version 1.0
 */

/**
 * 基于双向链表实现元素存取的容器
 *
 * @param <E>
 */
public class MyDoublyLinkedList<E> implements MyList<E> {
          
   


    /**
     * 定义双向链表节点对象
     */
    class Node<E> {
          
   
        E item; // 记录元素
        Node<E> prev; // 记录前一个节点对象
        Node<E> next; // 记录下一个节点对象

        public Node(Node<E> prev, E item, Node<E> next) {
          
   
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    private Node head; // 记录头节点
    private Node tail; // 记录尾节点
    private int size; // 记录元素个数

    /**
     * 向双向链表中添加元素的方法
     *
     * @param element
     */
    @Override
    public void add(E element) {
          
   
        linkLast(element);
    }

    /**
     * 将节点对象添加到双向链表的尾部
     */
    private void linkLast(E element) {
          
   
        Node t = this.tail; // 获取尾节点
        Node<E> node = new Node<>(t, element, null); // 创建节点对象
        this.tail = node; // 将新节点定义为尾节点 因为原来的尾节点被这个新节点替代了
        if (t == null) {
          
   
            // 说明一个节点都没有，这个还得是头节点
            this.head = node;
        } else {
          
   
            t.next = node;
        }
        this.size++;
    }

    /**
     * 根据指定位置获取元素
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
          
   
        this.checkIndex(index);
        // 根据位置查找节点对象
        Node<E> node = this.getNode(index);
        return node.item;
    }

    /**
     * 对index的合法性校验
     */
    private void checkIndex(int index) {
          
   
        if (!(index >= 0 && index < this.size)) {
          
   
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 根据位置获取指定节点对象
     */
    private Node getNode(int index) {
          
   
        // 判断当前位置距离头或者尾哪个节点更近  使用二分法
        if (index < (this.size >> 1)) {
          
   
            Node node = this.head;
            for (int i = 0; i < index; i++) {
          
   
                node = node.next;
            }
            return node;
        } else {
          
   
            Node node = this.tail;
            for (int i = this.size - 1; i > index; i--) {
          
   
                node = node.prev;
            }
            return node;
        }
    }

    /**
     * 返回元素的个数
     *
     * @return
     */
    @Override
    public int size() {
          
   
        return this.size;
    }

    /**
     * 删除元素
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
          
   
        // 对index进行合法性校验
        this.checkIndex(index);
        Node node = this.getNode(index); // 根据位置获取到节点对象
        // 获取节点对象的元素
        E item = (E) node.item;
        // 判断当前节点是否为头节点
        if (node.prev == null) {
          
   
            this.head = node.next;
        } else {
          
   
            node.prev.next = node.next;
        }
        // 判断当前节点是否为尾节点
        if (node.next == null) {
          
   
            // node.prev.next = null;
            this.tail = node.prev;
        } else {
          
   
            node.next.prev = node.prev;
        }
        // 当前节点断掉与他后继节点的连接
        node.next = null;
        // 当前节点断掉与直接前驱节点的连接
        node.prev = null;
        node.item = null;
        this.size--;
        return item;
    }

    /**
     * 在双向链表的头添加元素
     */
    public void addFirst(E element) {
          
   
        this.linkFirst(element);
    }

    /**
     * 在链表的头添加元素
     *
     * @param element
     */
    public void linkFirst(E element) {
          
   
        // 获取头节点对象
        Node head = this.head;
        Node<E> eNode = new Node<>(null, element, head);
        // 将新节点定义为头节点
        this.head = eNode;
        if (head == null) {
          
   
            // 如果为空，说明该链表中一个节点都没有 也就是该头节点也是尾节点
            this.tail = eNode;
        } else {
          
   
            head.prev = eNode;
        }
        this.size++;
    }

    /**
     * 在链表的尾部添加元素
     *
     * @param element
     */
    public void addLast(E element) {
          
   
        this.linkLast(element);
    }

    public static void main(String[] args) {
          
   
        MyDoublyLinkedList<String> list = new MyDoublyLinkedList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list.remove(2));
        System.out.println(list.size);
        for (int i = 0; i < list.size(); i++) {
          
   
            System.out.println(list.get(i));
        }
    }
}

谢谢您的观看。