简单实现一下单链表

链表结构

链式存储结构是基于指针实现的。我们把一个数据元素和一个指针称为结点。链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来。链式存储结构的线性表称为链表

链表类型

根据链表的构造方式的不同可以分为：

1. 单向链表
2. 单向循环链表
3. 双向循环链表

单链表

单链表是构成链表的每个结点只有一个指向直接后继结点的指针。单链表的表示方法，单链表中每个结点的结构：

image.png

单链表结构

单链表有带头结点结构和不带头结点结构两种。我们把指向单链表的指针称为单链表的头指针。头指针所指的不存放数据元素的第一个结点称作头结点。存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点。

image.png

节点类

单链表是由一个一个结点组成的，因此，要设计单链表类，必须先设计结点类。结点类的成员变量有两个：一个是数据元素，另一个是表示下一个结点的对象引用（即指针）。设计操作

1. 头结点的初始化
2. 非头结点的构造
3. 获取该结点指向的下个结点
4. 设置该结点指向的下个结点
5. 设置该结点的数据
6. 获取该结点的数据

顺序表和单链表的比较

顺序表的主要优点是支持随机读取，以及内存空间利用效率高；顺序表的主要缺点是需要预先给出数组的最大数据元素个数，而这通常很难准确作到。当实际的数据元素个数超过了预先给出的个数，会发生异常。另外，顺序表插入和删除操作时需要移动较多的数据元素。

和顺序表相比，单链表的主要优点是不需要预先给出数据元素的最大个数。另外，单链表插入和删除操作时不需要移动数据元素。 单链表的主要缺点是每个结点中要有一个指针，因此单链表的空间利用率略低于顺序表的。另外，单链表不支持随机读取，单链表取数据元素操作的时间复杂度为O（n）；而顺序表支持随机读取，顺序表取数据元素操作的时间复杂度为O（1）。

单链表的效率分析

在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：

image.png

删除单链表的一个数据元素时比较数据元素的平均次数为：

image.png
因此，单链表插入和删除操作的时间复杂度均为O（n）。另外，单链表取数据元素操作的时间复杂度也为O（n）。

单链表实现

单链表节点数据结构

package com.algorithm.list;
public class ListedNode {
    Object element;
    ListedNode next;
    public ListedNode(ListedNode next){
        this.next = next;
    }
    public ListedNode(Object element, ListedNode next){
        this.element = element;
        this.next = next;
    }
    public void setElement(Object element) {
        this.element = element;
    }
    public Object getElement() {
        return element;
    }
    public ListedNode getNext() {
        return next;
    }
    public void setNext(ListedNode next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return this.element.toString();
    }
}

单链表实现

package com.algorithm.list;
import java.time.temporal.Temporal;
public class LinkList implements List {
    /**
     * 头指针
     */
    private ListedNode head;
    /**
     * 当前节点对象
     */
    private ListedNode current;
    /**
     * 节点个数
     */
    private int size;
    /**
     * 创建空的链表
     */
    public LinkList() {
        // 初始化头节点，头指针指向头节点，当前节点对象等于头节点
        this.head = current = new ListedNode(null);
        // 单项链表初始长度
        this.size = 0;
    }
    @Override
    public int size() {
        return this.size;
    }

    /**
     * 获取当前对象的前一个节点，将当前节点定位到要操作节点的前一个元素，思考
     * @param index
     * @throws Exception
     */
    private void index(int index) throws Exception {
        // 小于-1，以首元节点索引为0，头节点为-1
        if(index < -1 || index > size - 1){
            throw new Exception("参数错误");
        }
        // 在头节点之后操作
        if(index == -1){
            return;
        }
        int j = 0;
        current = head.next;
        while(current != null && j < index){
            current = current.next;
            j++;
        }
    }
    @Override
   public void insert(int index, Object obj) throws Exception {
        // TODO Auto-generated method stub
        if(index <0 ||index >size)
        {
            throw new Exception("参数错误！");
        }
        //定位到要操作结点的前一个结点对象。
        index(index-1);
        current.setNext(new ListedNode(obj,current.next));
        size++;
    }
    @Override
    public void delete(int index) throws Exception {
        if(isEmpty()){
            throw new Exception("链表为空，无法删除!!");
        }
        check(index, 0, "参数范围错误");
        index(index - 1);
        current.setNext(current.next.next);
        this.size --;
    }
    private void check(int index, int i, String message) throws Exception {
        if (index < i || index > size) {
            throw new Exception(message);
        }
    }
    @Override
    public Object get(int index) throws Exception {
        check(index, 0, "参数范围错误");
        index(index);
        return current.getElement();
    }
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }
    public static void main(String[] args) throws Exception {
        LinkList list = new LinkList();
        for(int i = 0; i < 10; i++){
            int t = (int) ((Math.random()*100) % 100);
            list.insert(i,t);
            System.out.print(t+" ");
        }
        // 删除第五个元素
        list.delete(4);
        System.out.println("删除之后");
        for(int i = 0; i < list.size;i++){
            System.out.print(list.get(i) + " ");
        }
    }
}