链表结构简介

链表结构是由许多节点构成的，每个节点都包含两部分：

数据部分：保存该节点的实际数据。
地址部分：保存的是上一个或下一个节点的地址。

链表分类

单向链表
双向链表
双向循环链表

链表特点：

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
访问时只能通过头或者尾指针进入链表，并通过每个结点的指针域向后或向前扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

链表优缺点：
优点：数据元素的个数可以自由扩充、插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点：必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问，访问节点效率较低。

单向链表结构

 单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问 要通过从头部开始顺序读取

实现单向链表

//创建链表接口
public interface MyList <E>{
    void add(E element);
    E get(int index);
    int size();
    E remove(int index);
}

public class TestMyList<E> implements MyList<E>{
    private Node head;
    private int size;

    /**
     * 定义单向链表的节点内部类
     */
    class Node<E>{
        private E item;
        private Node next;
        //节点的构造方法
        Node(E item,Node next){
            this.item=item;
            this.next=next;
        }
    }


    /**
     * 找到尾节点
     */
    private Node getTail(){
        //头节点是否存在
        if(this.head==null){
            return null;
        }
        //查找尾节点
        Node node=this.head;
        while(true){
            if(node.next==null) break;
            node=node.next; //移动指针，指向下一个节点
        }
        return node;
    }
    /**
     * 添加元素
     * @param element
     */
    @Override
    public void add(E element) {
        //实例化一个节点
        Node<E> node=new Node<>(element,null);
        //找到尾节点
        Node tail=getTail();
        //节点的挂接
        if(tail==null){
            this.head=node;
        }else{
            tail.next=node;
        }
        //元素个数记录
        this.size++;
    }

    /**
     * 校验索引的合法性
     */
    private void checkIndex(int index){
        if(!(index>=0 && index<this.size)){
            throw new IndexOutOfBoundsException("index:"+index+"size:"+this.size);
        }
    }

    /**
     * 获取指定位置节点
     */
    private Node getNode(int index){
        Node<E> node=this.head;
        for(int i=0;i<index;i++){
            node=node.next;
        }
        return node;
    }

    /**
     * 根据索引位获取元素
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        //校验索引的合法性
        this.checkIndex(index);
        //根据指定索引获取节点
        Node<E> node=this.getNode(index);
        //将该节点返回
        return node.item;
    }

    /**
     * 获取链表元素个数
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }

    /**
     * 根据索引位删除元素
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        //索引合法性
        this.checkIndex(index);
        //根据位置获取节点对象
        Node<E> node = this.getNode(index);
        //获取该节点中的元素
        E item=node.item;
        //将该节点从单向链表中移除
        if(this.head==node){
            this.head=node.next;
        }else{
            Node<E> temp=this.head;
            for(int i=0;i<index-1;i++){
                temp=temp.next;
            }
            temp.next=node.next;
        }
        node.next=null; //释放节点
        //记录元素个数
        this.size++;
        //返回删除的元素
        return item;
    }

    public static void main(String[] args) {
        TestMyList<String> testMyList=new TestMyList<>();
        testMyList.add("a");
        testMyList.add("b");
        testMyList.add("c");
        testMyList.add("d");

        System.out.println(testMyList.size());
//        System.out.println(testMyList.remove(0));

        for(int i=0;i< testMyList.size();i++){
            System.out.println(testMyList.get(i));
        }
    }
}

双向链表结构

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接前驱和直接后继

实现双向链表