手写实现双向链表

àì夳堔傛蜴生んèń 2022-02-16 15:20 219阅读 0赞

前面一篇文章写到了实现单向链表，这篇文章记录一下实现双向链表。

双向链表顾名思义就是双向的链表，双向的意思是链表可以双向移动，即从前往后遍历和从后往前遍历均可实现。

双向链表的定义：*双向链表也叫[双链表][Link 1]，是链表的一种，它的每个数据结点中都有两个[指针][Link 2]，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向[循环链表][Link 3]。——来自百度百科 *

双向链表中每个节点分为三部分组成：第一部分是节点本身存储的数据，第二部部分是该节点的前一个节点的指针，第三部分是该节点下一个节点的指针。

双向链表的特点：

1.  和单向链表一样没有容量限制
2.  双向均可快速读写

至于线程安全的问题，由于是自定义实现，同步同步看个人喜好需要就行了。

双向链表的结构：

![20190422172706396.png][]

双向链表结构示意图

双向链表的操作：

1.插入新元素：将L1节点的Next指针指向新节点L4，将新节点L4的Pre指针指向L1，将新节点L4的Next指针指向L2，再将L2节点的Pre指针指向新节点L4。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70][]

双向链表插入新节点示意图

2.删除指定节点：将L1节点的Next指针指向L2节，将L3节点的Pre指针指向L2节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 1][]

下面再看看代码的实现：

自定义双向链表：

package dataStructure;
    
    import java.util.ConcurrentModificationException;
    import java.util.Iterator;
    import java.util.Objects;
    import java.util.function.Consumer;
    
    /**
     * Created by Viking on 2019/4/9
     * 实现双向链表
     *
     */
        public class MyBothLinkedList<E> implements Iterable<E>{
        private transient int size;
        private transient int modCount;
        private transient Node<E> first;
        private transient Node<E> last;
    
    
        public void addFirst(E e){
            linkFirst(e);
        }
        public void addLast(E e){
            linkLast(e);
        }
        public void add(E e){
            linkLast(e);
        }
        public void add(int index, E e){
            linkIndex(index,e);
        }
        public E getFirst(){
            return first.item;
        }
        public E getLast(){
            return last.item;
        }
        public E get(int index){
            return node(index).item;
        }
        public int size(){
            return size;
        }
        public boolean isEmpty(){
            return size==0;
        }
        public E removeFirst(){
            return unlinkFirst();
        }
        public E removeLast(){
            return unlinkLast();
        }
        public E remove(int index){
            checkIndexOfLink(index);
            return unlinkIndexOfLink(index);
        }
        public Iterator<E> myIterator(){
            return new MyIterator(0);
        }
        public Iterator<E> myIterator(int index){
            return new MyIterator(index);
        }
    
        //实现foreach循环
        @Override
        public Iterator<E> iterator() {
            return new MyIterator(0);
        }
    
        /**
         * Links e as first element.
         */
        private void linkFirst(E e) {
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(e,null,f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
        /**
         * Links e as last element.
         */
        private void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>( e,l, null);
    
            if (l == null)
                first = newNode;
            else if (first==last){
                first.next = newNode;
                newNode.prev = last;
            }else{
                l.next = newNode;
                newNode.prev = l;
            }
            last = newNode;
            size++;
            modCount++;
        }
        private void linkIndex(int index, E e){
            if (index < 0 || index > size) throw new UnsupportedOperationException();
            if (index==0) linkFirst(e);
            else if (index==size) linkLast(e);
            else {
                Node<E> node = first;
                for (int i = 1;i<index;i++){
                    node = node.next;
                }
                Node<E> newNode = new Node<>(e,node,node.next);
                node.next = newNode;
                newNode.next.prev = newNode;
            }
            size++;
            modCount++;
        }
        private void checkIndexOfLink(int index){
            if (index<0||index>=size) throw new IndexOutOfBoundsException("index:"+index+" of size:"+size);
        }
        private Node<E> node(int index){
            checkIndexOfLink(index);
            Node<E> node = first;
            for (int i =0;i<index;i++){
                node = node.next;
            }
            return node;
        }
        private E unlinkFirst(){
            Node<E> f = first;
            first=f.next;
            first.prev = null;
            size--;
            modCount++;
            return f.item;
        }
        private E unlinkLast(){
            Node<E> l = last;
            last = l.prev;
            last.next = null;
            modCount++;
            size--;
            return l.item;
        }
        private E unlinkIndexOfLink(int index){
            if (index==0) return unlinkFirst();
            else if (index==size-1) return unlinkLast();
            else {
                Node<E> node = first;
                for (int i = 1; i <= index; i++) {
                    node = node.next;
                }
                node.prev.next = node.next;
                node.next.prev = node.prev;
                size--;
                modCount++;
                return node.item;
            }
    
        }
        public String toString(){
            StringBuilder str = new StringBuilder();
            if (size==0) str.append("[]");
            else {
                str.append("[");
                Node<E> node = first;
                str.append(node.item);
                for (int i=1 ;i<size;i++){
                    node = node.next;
                    str.append(",");
                    str.append(node.item);
                }
                str.append("]");
            }
            return str.toString();
        }
        /**
         * 链表的节点
         */
        private static class Node<E> {
            E item;
            Node<E> prev;
            Node<E> next;
    
            Node(E element,Node<E> prev, Node<E> next) {
                this.item = element;
                this.prev = prev;
                this.next = next;
            }
        }
    
        private class MyIterator implements Iterator<E>{
            private Node<E> lastReturned;
            private Node<E> next;
            private int nextIndex;
            private int expectedModCount = modCount;
            private MyIterator(int index){
                next = index == size?null:node(index);
                this.nextIndex = index;
            }
            @Override
            public boolean hasNext() {
                return nextIndex < size;
            }
    
            @Override
            public E next() {
                checkForComodification();
                lastReturned = next;
                next = next.next;
                nextIndex++;
                return lastReturned.item;
            }
    
            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                while (modCount == expectedModCount && nextIndex < size) {
                    action.accept(next.item);
                    lastReturned = next;
                    next = next.next;
                    nextIndex++;
                }
                checkForComodification();
            }
    
            final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }
    }

编写一个测试类：

import dataStructure.MyBothLinkedList;
    
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    
    /**
     * Created by Viking on 2019/4/11
     * 测试双向链表
     */
    public class TestBothLinkedList {
        public static void main(String[] args) {
            MyBothLinkedList<String> list = new MyBothLinkedList<>();
            System.out.println("list.size:"+list.size()+"\tFirst:"+null+"\tLast:"+null+"\t"+list);
            list.add("First");
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.add("Second");
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.add("Third");
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.addFirst("new First");
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.addLast("last");
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.add(3,"index of 3");
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            System.out.println("list.get(0):"+list.get(0)+"\tlist.get(1):"+list.get(1)+"\tlist.get(2):"+list.get(2));
            list.removeFirst();
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.removeLast();
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.remove(0);
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            list.remove(1);
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            Iterator<String> iterator = list.myIterator();
            //迭代器循环
            while (iterator.hasNext()){
                System.out.println(iterator.next());
            }
            System.out.println("list.size:"+list.size()+"\tFirst:"+list.getFirst()+"\tLast:"+list.getLast()+"\t"+list);
            //foreach循环
            for (String s : list){
                System.out.println(s);
            }
            //连续下标索引取值
            for (int i = 0;i < list.size();i++){
                System.out.println(list.get(i));
            }
        }
    }

测试结果：

list.size:0	First:null	Last:null	[]
    list.size:1	First:First	Last:First	[First]
    list.size:2	First:First	Last:Second	[First,Second]
    list.size:3	First:First	Last:Third	[First,Second,Third]
    list.size:4	First:new First	Last:Third	[new First,First,Second,Third]
    list.size:5	First:new First	Last:last	[new First,First,Second,Third,last]
    list.size:6	First:new First	Last:last	[new First,First,Second,index of 3,Third,last]
    list.get(0):new First	list.get(1):First	list.get(2):Second
    list.size:5	First:First	Last:last	[First,Second,index of 3,Third,last]
    list.size:4	First:First	Last:Third	[First,Second,index of 3,Third]
    list.size:3	First:Second	Last:Third	[Second,index of 3,Third]
    list.size:2	First:Second	Last:Third	[Second,Third]
    Second
    Third
    list.size:2	First:Second	Last:Third	[Second,Third]
    Second
    Third
    Second
    Third

[Link 1]: https://baike.baidu.com/item/%E5%8F%8C%E9%93%BE%E8%A1%A8/5827945
[Link 2]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88/2878304
[Link 3]: https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8/3228465
[20190422172706396.png]: /images/20220216/9ad05da3c6104617a1fb9f09518fca45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70]: /images/20220216/42dfa23d6034496285468e507847c907.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yX19WaWtpbmc_size_16_color_FFFFFF_t_70 1]: /images/20220216/889dc98a7eee4a42bdcdd8197dd1e6dd.png