《大话数据结构》之双向链表

大猫的Java笔记

发布于 2020-09-30 01:49:10

3500

发布于 2020-09-30 01:49:10

1. 简介

前面讲了单向链表实际上就是在保存数据的同时并保存下一个元素的地址值来进行关联，这样就像锁链一样一个套着一个，但是他只能通过当前地址找到下一个元素，不能反向找，就好比我存了我儿子的电话，而我儿子对我不怎么上心手机一直没有存储我的电话，所以他只能等我去联系他，从来不会主动来联系我，因为没办法进行联系。

有一天我很生气，因为我生日他都不给我打电话，因为没有我的联系方式，事后他很内疚，然后存储了我的联系方式，而这就是双向链表就是你可以找到我我也可以找到你，也就是在单向链表中再加一个地址用于存储上一个数据的地址。

双向链表结构如下。

2. 优缺点

和单向链表一样，他的插入和删除操作效率是比线性表的顺序存储要快的，却比单向链表慢因为他在插入和删除时需要维护上一个地址和下一个地址，而单向只需要维护下一个地址，但是他相比单向链表而言可以通过当前的节点找到上一个数据，时间复杂度为O(1),而单向链表要找到上一个节点的数据，那么就需要从头遍历，所以是O(n)。

3. 使用Java代码实现双向链表

package com.bigcat;
/** * 双向链表实现新增 插入 删除 查询 * @param <E> * @author damao * @date 2019/11/13 */public class TwoWayLinkedList<E>{
    /**     * 头链表，用于后面的遍历     */    Node<E> firstNode;
    private  Node<E> prevAddress = null;
    private int size = 0;

    public boolean add(E e){        if(firstNode == null){            prevAddress = firstNode = new Node(null,null,e);            size++;            return true;        }        prevAddress = prevAddress.next = new Node(prevAddress,null,e);        size++;        return true;    }

    public boolean add(int index,E e){        if(index <= 0){            throw new RuntimeException("Index must be greater than zero");        }        if(firstNode == null || index == 1){            firstNode = new Node(null, firstNode, e);            size++;            return true;        }        Node<E> theNode = firstNode.next;        Node<E> prevNode = firstNode;        for (int i = 2; i <= index; i++) {            if(i == index){                Node<E> newNode = new Node(prevNode,theNode,e);                theNode.prev = newNode;                prevNode.next = newNode;                size++;                return true;            }            theNode = theNode.next;            prevNode = theNode.prev;        }        return false;    }

    public boolean remove(int index){        if(index <= 0 || index > size){            throw new RuntimeException("Out of index range");        }        if(index == 1){            Node<E> newfirstNode = firstNode.next;            firstNode.next = null;            firstNode.value = null;            firstNode = newfirstNode;            size--;            return true;        }        Node<E> theNode = firstNode.next;        Node<E> prevNode = firstNode;        Node<E> nextNode = theNode.next;        for (int i = 2; i <= index; i++) {            if(i == index){                theNode.value = null;                prevNode.next = theNode.next;                if(i != size) {                    theNode.next.prev = prevNode;                }                theNode.next = null;                theNode.prev = null;                size--;                return true;            }            theNode = nextNode.next;            prevNode = theNode.prev;            nextNode = theNode.next;        }        return false;    }

    public E get(int index){        if(index <= 0 || index > size){            throw new RuntimeException("Out of index range");        }        Node<E> theNode = firstNode;        for (int i = 1; i <= index; i++) {            if(i == index){                  return theNode.value;            }            theNode = theNode.next;        }        return null;    }


    public int getSize(){        return this.size;    }

    private static class Node<E>{        Node<E> prev;        Node<E> next;        E value;
        public Node(Node<E> prev, Node<E> next, E value) {            this.prev = prev;            this.next = next;            this.value = value;        }    }
}

测试结果如下