链表

链表是一种插入和删除都比较快的数据结构，缺点是查找比较慢。内存空间是不连续的。数据集比较大，碎片化比较严重。

链表结构图：

1.png

单链表

删除图：

3.png

添加图：

4.jpeg

代码实现类

//节点类
public class LinkNode {
    public int value;
    public LinkNode next;
    public LinkNode() {
    }

    public LinkNode(int value) {
        this.value = value;
    }

    public void display(){
        System.out.print(value + "");
    }
}
//链表的封装类
public class LinkList {
    public LinkNode first;

    public LinkList() {
        this.first = new LinkNode();
    }

    /**
     * 增加操作
     * 局部变量temp为移动指针
     */
    public void insert(LinkNode linkNode) {
        //把头结点看成指针
        LinkNode temp = first;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = linkNode;
    }

    /**
     * insertNodeByIndex:在链表的指定位置插入结点。
     * 插入操作需要知道1个结点即可，当前位置的前一个结点
     * index:插入链表的位置，从1开始
     * node:插入的结点
     */
    public void insertNodeByIndex(int index, LinkNode linkNode) throws Exception {
        if (index <= 0 || index > length()+1) {
            throw new Exception("插入位置不合理");
        }
        int location = 1;
        LinkNode temp = first;
        while (first.next != null) {
            if (location++ == index) {
                linkNode.next = temp.next;
                temp.next = linkNode;
                return;
            }
            temp = temp.next;
        }
    }

    /**
     * 通过index删除指定位置的结点,跟指定位置增加结点是一样的，先找到准确位置。然后进行删除操作。
     * 删除操作需要知道1个结点即可：和当前位置的前一个结点。
     *
     * @param index：链表中的位置，从1开始
     */
    public void delNodeByIndex(int index) throws Exception {
        if (index <= 0 || index > length()) {
            throw new Exception("插入位置不合理");
        }
        LinkNode node = first;
        int location = 1;
        while (first.next != null) {
            while (node.next != null) {
                if (location++ == index) {
                    node.next = node.next.next;
                    return;
                }
                node = node.next;
            }
        }
    }


    //计算当前列表长度
    public int length() {
        int length = 0;
        LinkNode temp = first;
        while (temp.next != null) {
             temp = temp.next;
              length++;
        }
        return length;
    }
    /**
     * 遍历单链表，打印所有data
     */
    public void print(){
        LinkNode temp = first.next;
        while(temp != null){
            System.out.print(temp.value+",");
            temp = temp.next;
        }
        System.out.println();
    }
}
//测试
 public static void main(String[] args) throws Exception {
        LinkList linkList = new LinkList();
        linkList.insert(new LinkNode(1));
        linkList.insert(new LinkNode(2));
        linkList.insert(new LinkNode(3));
        linkList.print();
        System.out.print(linkList.length()+"");
        linkList.delNodeByIndex(3);
        linkList.print();
        linkList.insertNodeByIndex(4,new LinkNode(4));
        linkList.print();
    }

双端链表

双端链表与双向链表是完全不同的两个概念。双端链表与单链表的区别在于它不只第一个链结点有引用，还对最后一个链结点有引用。

如图：

2.png

有序链表

对于某些应用来说，在链表中保持数据有序是很有用的，具有这个特性的链表叫作“有序链表”

有序链表优于有序数组的地方在于插入的效率更高（不需要像数组那样移动元素），另外链表可以灵活地扩展大小，而数组的大小是固定的。但是这种效率的提高和灵活的优势是以算法的复杂为代价的

双向链表

每个链结点既有下一个链结点的引用，也有上一个链结点的引用。

整体结构如图：

1.png

表头插入操作如下图：

4.jpeg
在表尾插入与之类似，是表头插入的镜像操作
中间插入：
6.jpeg

删除操作：

7.png