一：LinkedList

1.定义head节点，用于存放头节点信息

   /**
     * head用于存放头节点信息
     */
    private Node head;

2.定义size，用于表示链表长度

   /**
     * 链表的长度
     */
    private Integer size = 0;

3.定义Node对象，用于表示某个节点的所有属性

class Node {
        //存放数据
        E data;
        //前继节点
        Node next;
        //后继节点
        Node prev;
        //构造器
        public Node(E e){
            data = e;
        }
    }

• Node用于描述表中的一个节点
• 其中，data用于存放于元素
• next是存放前继节点
• prev用于存放指向其后继节点

4.将元素追加到链表的末尾

    /**
     * 将元素追加到链表的末尾
     * @param e 被添加的元素
     * @return 添加成功，返回true
     */
    public boolean add(E e){
        //将元素封装成一个节点
        Node node = new Node(e);
        //如果链表为空，则新节点就是头节点
        if(head == null){
            head = node;
            head.next = node;
            head.prev = node;
            //链表的长度加1
            size ++;
            return true;
        }
        //找到末尾节点地址
        Node last = head.prev;
        //将新节点添加到未节点后面
        last.next = node;
        node.next = head;
        head.prev = node;
        node.prev = last;
        //链表的长度加1
        size ++;
        return true;
    }

5.将元素插入到指定下标处

 /**
     * 将元素插入到指定下标处
     * @param index
     * @param e
     */
    public void add(int index,E e){
        if( index < 0 || index > size ){
            throw new IndexOutOfBoundsException("数组下标越界异常");
        }
        if(index == size){
           add(e);
        }
        //将元素封装成一个节点
        Node node = new Node(e);
        Node next = getNode(index);
        Node prev = next.prev;
        next.prev = node;
        node.prev = prev;
        prev.next = node;
        node.next = next;
        if(index == 0){
            head = node;
        }
        size ++;
    }

6.返回指定位置的节点

   /**
     * 返回指定位置的节点
     * @param index
     * @return
     */
    private Node getNode(Integer index) {
        //从头结点开始遍历
        Node node = this.head;
        //此时可以用移位运算
        //为了提升性能，可以通过比较index与链表的长度的一半来决定是向前遍历还是向后遍历
        if (index < size >>1){
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            for (int i = size; i > index ; i--) {
                node = node.prev;
            }
        }
        return node;
    }

7.移除指定位置处的元素

   /**
     * 移除指定位置处的元素
     * @return
     */
    public E remove(Integer index){
        if(index < 0||index >=size){
            throw new IndexOutOfBoundsException("数组下标越界异常");
        }
        //如果链表只有一个元素,则删除该节点以后，需要将head设置为null,并返回删除的元素
        if (size == 1) {
            E data = head.data;
            head = null;
            size --;
            return data;
        }
        //找到要删除的节点
        Node node = this.getNode(index);
        //找到该节点的前驱节点和后继节点
        Node next = node.next;
        Node prev = node.prev;
        //将该节点删除(其实就是在prev和next之间建立引用关系)
        prev.next = next;
        next.prev = prev;
        //如果被删除的元素为头节点,则其下一个节点为头节点
        if(index == 0){
            head = next;
        }
        //链表长度减1
        size--;
        return node.data;
    }

8.重写toString方法

@Override
    public String toString(){
        if(head == null){
            return "[]";
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        stringBuilder.append(head.data);
        Node node = head.next;
        while(node.next != head){
            stringBuilder.append("," + node.data);
            //继续查找下个节点
            node = node.next;
        }
        return stringBuilder.append("]").toString();
    }

9.源码在此

package com.sysg.list;
/**
 * @author 77916
 * 测试linkedList
 */
public class LinkedList<E> {
    /**
     * head用于存放头节点信息
     */
    private Node head;
    /**
     * 链表的长度
     */
    private Integer size = 0;

    /**
     *  Node用于描述表中的一个节点
     *  其中，data用于存放于元素
     *  next是存放前继节点
     *  prev用于存放指向其后继节点
     */
    class Node {
        //存放数据
        E data;
        //前继节点
        Node next;
        //后继节点
        Node prev;
        //构造器
        public Node(E e){
            data = e;
        }
    }

    /**
     * 将元素追加到链表的末尾
     * @param e 被添加的元素
     * @return 添加成功，返回true
     */
    public boolean add(E e){
        //将元素封装成一个节点
        Node node = new Node(e);
        //如果链表为空，则新节点就是头节点
        if(head == null){
            head = node;
            head.next = node;
            head.prev = node;
            //链表的长度加1
            size ++;
            return true;
        }
        //找到末尾节点地址
        Node last = head.prev;
        //将新节点添加到未节点后面
        last.next = node;
        node.next = head;
        head.prev = node;
        node.prev = last;
        //链表的长度加1
        size ++;
        return true;
    }

    /**
     * 将元素插入到指定下标处
     * @param index
     * @param e
     */
    public void add(int index,E e){
        if( index < 0 || index > size ){
            throw new IndexOutOfBoundsException("数组下标越界异常");
        }
        if(index == size){
           add(e);
        }
        //将元素封装成一个节点
        Node node = new Node(e);
        Node next = getNode(index);
        Node prev = next.prev;
        next.prev = node;
        node.prev = prev;
        prev.next = node;
        node.next = next;
        if(index == 0){
            head = node;
        }
        size ++;
    }

    /**
     * 返回指定下标处的元素
     * @param index 下标，从0开始
     * @return 对应位置处的元素
     */
    public E get(Integer index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("数组下标越界异常");
        }
        Node node = getNode(index);
        //返回该节点存放的数据
        return node.data;
    }

    /**
     * 移除指定位置处的元素
     * @return
     */
    public E remove(Integer index){
        if(index < 0||index >=size){
            throw new IndexOutOfBoundsException("数组下标越界异常");
        }
        //如果链表只有一个元素,则删除该节点以后，需要将head设置为null,并返回删除的元素
        if (size == 1) {
            E data = head.data;
            head = null;
            size --;
            return data;
        }
        //找到要删除的节点
        Node node = this.getNode(index);
        //找到该节点的前驱节点和后继节点
        Node next = node.next;
        Node prev = node.prev;
        //将该节点删除(其实就是在prev和next之间建立引用关系)
        prev.next = next;
        next.prev = prev;
        //如果被删除的元素为头节点,则其下一个节点为头节点
        if(index == 0){
            head = next;
        }
        //链表长度减1
        size--;
        return node.data;
    }
    /**
     * 获得链表的长度
     * @return
     */
    public int size(){
        return size;
    }
    @Override
    public String toString(){
        if(head == null){
            return "[]";
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        stringBuilder.append(head.data);
        Node node = head.next;
        while(node.next != head){
            stringBuilder.append("," + node.data);
            //继续查找下个节点
            node = node.next;
        }
        return stringBuilder.append("]").toString();
    }

    /**
     * 返回指定位置的节点
     * @param index
     * @return
     */
    private Node getNode(Integer index) {
        //从头结点开始遍历
        Node node = this.head;
        //此时可以用移位运算
        //为了提升性能，可以通过比较index与链表的长度的一半来决定是向前遍历还是向后遍历
        if (index < size >>1){
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            for (int i = size; i > index ; i--) {
                node = node.prev;
            }
        }
        return node;
    }

}