Java

linkedList（链表）底层是用双向链表实现的存储。是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。

public class SxtlinkedList {
    private Node first;
    private Node last;

    private int size;

    public void add(E element){
        Node node = new Node(element);
        if(first == null){
//            node.previous = null;
//            node.next = null;
            first = node;
            last = node;
        }else {
            last.next = node;
            node.previous = last;
            node.next = null;
            last = node;
        }
        size++;

    }

    public Object get(int index){
        checkIndex(index);
        Node temp = getNode(index);
        return  temp!=null?(E)temp.object:null;
    }

    public void remove(int index){
        checkIndex(index);
        Node temp=getNode(index);
        Node up = temp.previous;
        Node down = temp.next;
        if(up!=null){
            up.next = down;
        }else {
            first = down;
        }
        if(down!=null){
            down.previous = up;
        }else {
            last = up;
        }
        size--;
    }

    public void add(int index , E element){
        Node temp=getNode(index);
        Node newNode = new Node(element);
        if(temp!=null ){
            if(index == 0){
                temp.previous= newNode;
                first = newNode;
                newNode.next = temp;
            }else if(index == size){
                temp.next = newNode;
                newNode.previous = temp;
                newNode.next = null;
                last = newNode;
            }else{
                Node up = temp.previous;
                up.next = newNode;
                newNode.previous = up;
                newNode.next = temp;
                temp.previous = newNode;
            }


        }


        size++;
    }



    public  Node getNode(int index){
        checkIndex(index);
        Node temp = new Node(null);

        if(index<(size/2)){
            temp = first;
            for (int i = 0; i index ; i--) {
                temp = temp.previous;
            }

        }
        return temp;
    }




    @Override
    public String toString() {
        Node temp = first;
        StringBuilder  stringBuilder = new StringBuilder("[");
        while (temp != null){
            stringBuilder.append(temp.object+",");
            temp = temp.next;
        }
        stringBuilder.setCharAt(stringBuilder.length() - 1,']');
        return stringBuilder.toString();
    }

    private boolean checkIndex(int index){
        if(index<0||index>=size){
            throw new RuntimeException("索引数字不合法"+index);
        }
        return true;
    }


    public static void main(String[] args) {
        SxtlinkedList linkedList = new SxtlinkedList<>();
        linkedList.add("a");
        linkedList.add("b");
        linkedList.add("c");
        System.out.println(linkedList);
        System.out.println(linkedList.get(2));

        linkedList.remove(1);
        System.out.println(linkedList);

        linkedList.add(0,"1");
        linkedList.add(2,"d");
        linkedList.add(3,"e");
        System.out.println(linkedList);
    }
}