自己实现双向链表Link-通俗易懂

前言

链表中的每个节点即指向前面一个节点，也指向后面一个节点，就像丢手绢游戏一样，每个人都手拉手 。双向链表结构和单向链表的区别：最后一个结点的链接地址上，单向链表是null,而双向链表是表头的链接地址。

删除之后 index节点的上一个（20这个节点）的下一个指向index节点的下一个
index节点的下一个（40这个节点）的上一个指向index节点的上一个

在index（20这个节点）之前添加
添加之后 新元素为15这个节点
新元素的下一个指向index（20这个节点）
新元素的上一个指向index的上一个（10这个节点）
系元素的上一个（10这个节点）的下一个指向新元素
新元素的下一个（20这个节点）的上一个指向新元素

图片来源：https://blog.csdn.net/defineshan/article/details/52266184

Demo(双向链表)

package com.cxx.list;
/**
 * @Author: cxx
 * 双向链表
 * @Date: 2018/6/7 20:31
 */
public class DoubleLinkList {
    private static class Node{
        Object value;
        Node prev = this;
        Node next = this;
        Node(Object v){
            value=v;
        }
        public String toString(){
            return value.toString();
        }
    }
    private Node head = new Node(null);//头结点
    private int size;//链表大小

    //添加到链表的头部
    public boolean addFirst(Object o)
    {
        addAfter(new Node(o),head);
        return true;
    }
    //添加到链表的尾部
    public boolean addLast(Object o){
        addBefore(new Node(o),head);
        return true;
    }

    //返回链表大小
    public int size(){
        return size;
    }

    public String toString(){
        StringBuffer s = new StringBuffer("[");
        Node node=head;
        for (int i=0;i<size;i++){
            node=node.next;
            if (i>0)
                s.append(", ");
            s.append(node.value);
        }
        s.append("]");
        return s.toString();
    }

    //查找链表元素
    private Node getNode(int index){
        if (index<0||index>=size)
            throw new IndexOutOfBoundsException();
        Node node=head.next;
        for(int i=0;i<index;i++){
            node=node.next;
        }
        return node;
    }

    //在某元素前添加元素
    private void addBefore(Node newNode,Node node){
        newNode.prev=node.prev;
        newNode.next=node;
        newNode.next.prev=newNode;
        newNode.prev.next=newNode;
        size++;
    }

    public boolean add(Object o){
        return addLast(o);
    }

    //将元素加到指定位置
    public boolean add(int index,Object o){
        addBefore(new Node(o),getNode(index));
        return true;
    }

    //取到指定位置的元素值
    public Object get(int index){
        return getNode(index).value;
    }

    //在某元素后添加元素
    private void addAfter(Node newNode,Node node){
        newNode.prev=node;
        newNode.next=node.next;
        newNode.next.prev=newNode;
        newNode.prev.next=newNode;
        size++;
    }

    //移除特定的元素
    private void removeNode(Node node){
        node.next.prev=node.prev;
        node.prev.prev=node.next;
        node.prev=null;
        node.next=null;
        size--;
    }
}

---

测试代码

package com.cxx.list;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
 * @Author: cxx
 * @Date: 2018/6/7 17:08
 */
public class MyTest {
    public static void main(String[] args) {
        DoubleLinkList dll = new DoubleLinkList();
        dll.add("A");
        dll.add("B");
        dll.add("C");
        System.out.println(dll.toString());
        dll.addFirst("D");
        System.out.println(dll.toString());
        dll.addLast("E");
        System.out.println(dll.toString());
        dll.add(2,"F");
        System.out.println(dll.toString());

    }
}

---

效果截图