链表Linked List

真正的动态数据结构！
概念：

1. 是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。
2. 每个链表都包含多个节点，节点包含两个部分。
   1. 数据域：存储节点含有的信息。
   2. 引用域：存储下一个节点或者上一个节点的地址。

特点：

• 获得数据麻烦，需要遍历查找，比数组慢。
• 方便插入、删除。

分类：

1. 单向链表
2. 双向链表
3. 环形链表
4. 双向环形链表

优点：
真正的动态，不需要处理固定容量的问题。
缺点：
丧失了随机访问的能力。
实现原理;

1. 创建一个节点类。
   1. 数据域：链表中存储的信息。
   2. 节点域：相当于指针。单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向上一个和下一个。
2. 创建一个链表类。
   1. 头结点
   2. 为节点
   3. 大小

单向链表节点类：

public class Node{
    public Object data;
    public Node next;
    public Node(Object o){
        this.data = o;
    }
}

双向链表节点类：

public class Node{
    public Object o;
    public Node next;
    public Node pre;
    public Node(Object o){
        this.o = o;
        this.next = null;
        this.next = null;
    }
}

设计一个简单链表

//链表
package com.qingFeng;
public class LinkedList<E> {
    private class Node{
        public E e;
        public Node next;
        public Node(E e , Node next){
            this.e = e;
            this.next = next;
        }
        public Node(E e){
            this(e , null);
        }
        public Node() {
            this(null , null);
        }
        @Override
        public String toString(){
            return e.toString();
        }
    }
    //虚拟头节点
    private Node dummyHead;
    private int size;
    public  LinkedList(){
        dummyHead = new Node(null,null);
        size = 0;
    }
    //获取链表中元素的个数
    public int getSize(){
        return size;
    }
    //返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //在链表头添加新的元素e
    public void addFirst(E e){
        /*Node node = new Node(e);
        node.next = head;
        head = node;*/
        add(0,e);
    }
    //在链表中间添加元素e
    public void add(int index, E e){
        if (index < 0 || index > size){
            throw new IllegalArgumentException("add failed. Illegal index.");
        }
        Node prev = dummyHead;
        for (int i = 0 ; i < index ; i ++){
            prev = prev.next;
        }
        /*Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;*/
        prev.next = new Node(e,prev.next);
        size ++;
    }
    //在链表末尾添加新的元素e
    public void addLast(E e){
        add(size, e);
    }
    //获取链表的第index位置的元素
    public E get(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }
        Node cur = dummyHead.next;
        for (int i = 0 ; i < index ; i ++){
            cur = cur.next;
        }
        return cur.e;
    }
    //获取链表的第一个元素
    public E getFirst(){
        return get(0);
    }
    //获取链表最后一个元素
    public E getLast(){
        return get(size - 1);
    }
    //修改链表第index位置的元素为e
    public void set(int index , E e){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Set failed. Illegal index.");
        }
        Node cur = dummyHead.next;
        for (int i = 0 ; i < index ; i ++){
            cur = cur.next;
        }
        cur.e = e;
    }
    //查找链表中是否有元素e
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while (cur != null){
            if (cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //从链表中删除index位置的元素，返回删除的元素
    public E remove(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Remove failed. Index is illegal");
        }
        Node prev = dummyHead;
        for (int i = 0 ; i < index ; i ++){
            prev = prev.next;
        }
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;
        return retNode.e;
    }
    //从链表中删除第一个元素
    public E removeFirst(){
        return remove(0);
    }
    //从链表删除最后一个元素
    public E removeLast(){
        return remove(size - 1);
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        /*Node cur = dummyHead.next;
        while (cur != null){
            res.append(cur + "——>");
            cur = cur.next;
        }*/
        for (Node cur = dummyHead.next ; cur != null ; cur = cur.next){
            res.append(cur + "——>");
        }
        res.append("null");
        return res.toString();
    }
}
//客户端
package com.qingFeng;
public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0 ; i < 5 ; i ++){
            linkedList.addLast(i);
        }
        System.out.println(linkedList);
        linkedList.remove(1);
        System.out.println(linkedList);
        linkedList.removeLast();
        System.out.println(linkedList);
    }
}