链表

链表说明

链表是一种用于存储数据集合的数据结构。链表有以下属性：

• 相邻元素之间通过指针连接
• 最后一个元素的后继指针值为NULL在程序执行过程中，链表的长度可以增加或缩小。
• 链表的空间能够按需分配（直到系统内存耗尽）。
• 没有内存空间的浪费（但是链表中的指针需要一些额外的内存开销）

链表抽象数据类型

链表抽象数据类型中的操作如下：

链表的主要操作

• ·插入：插入一个元素到链表中。
• ·删除：移除并返回链表中指定位置的元素。

链表的辅助操作

• 删除链表：移除链表中的所有元素（清空链表）。
• 计数：返回链表中元素的个数。
• 查找：寻找从链表表尾开始的第n个结点（node）.

数组和链表的对比

数组概述

? 整个数组所有的元素都存储在操作系统分配的一个内存块中。通过使用特定元素的索引作为数组下标，可以在常数时间内访问数组元素。

• 为什么能在常数时间内访问数组元素

  • 访问一个数组元素只需要将该数组基地址加上其偏移量就可以获得该元素内存地址
    • 因为该过程只需要一次乘法一次加法都是常数时间，所以可以认为是在常数时间内完成

• 数组的优点

  • 简单易用
  • 访问元素快

• 数组的缺点

  • 大小固定 数组的大小是静态的-在使用前确定数组大小
  • 分配一个连续的空间块
  • 基于位置的插入操作实现复杂

• 动态数组

  • 实现的简单方法是初始化一个固定大小的数组一但满了就创建一个二倍原数组的新数组，同样如果存储小于一半就将数组大小减少一半

• 链表的优点

  • 相比数组的空间确定，链表的空间是可变的
  • 插入操作比数组简单很多

• 链表的缺点

  • 访问单个元素的时间开销问题
    • 数组的访问开销为O(1)而链表最差情况为O(n)
  • 检索数据开销大
  • 额外指针需要额外内存

单向链表

? 链表通常是指单向链表，它包含多个结点，每个结点有一个指向后继元素的next（下一个）指针。表中最后一个结点的next指针值为NULL，表示该链表的结束。

链表类型声明：

public class ListNode {
    private int data;
    private ListNode next;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}

链表的基本操作

• 遍历链表。
• 在链表中插入一个元素。
• 从链表中删除一个元素。

链表的遍历

假设表头结点的指针指向链表中的第一个结点。遍历链表需完成以下步骤。

• 沿指针遍历。
• 遍历时显示结点的内容（或计数）。
• 当next指针的值为NULL.时结束遍历。

int ListLength(ListNode headNode) {	//遍历然后返回链表长度
    int length = 0;
    ListNode currentNode = headNode;
    while (currentNode != null){
        length++;
        currentNode = currentNode.getNext();
    }
    return length;
}

时间复杂度为O（n），用于扫描长度为n的链表。空间复杂度为0（1），仅用于创建临时变量。

单向链表的插入

单向链表的插入操作可分为以下3种情况：

• 在链表的表头前插入一个新结点（链表开始处）。

• 在链表的表尾后插入一个新结点（链表结尾处）。

• 在链表的中间插入一个新结点（随机位置）。

• 都可以归结为最后一种状态

实现方法新位指向前位的下一位，前位指向新位。

ListNode InsertInLinkedList(ListNode headNode,ListNode nodeToInsert,int position) {
    if(headNode == null){//链表为空直接插入然后返回插入节点-因为java属性引用默认为空所以这里不用置null
        return nodeToInsert;
    }
    int size = ListLength(headNode);
    if(position > size+1 | position < 1){
        System.out.println("插入位置错误！");
        return headNode;
    }
    if(position == 1){//在链表开头插入将插入指向头然后将插入节点返回出去
        nodeToInsert.setNext(headNode);
        return nodeToInsert;
    }else{//在除开始以外任意节点插入
        ListNode previousNode = headNode;
        int count = 1;
        while (count < position-1){
            previousNode = previousNode.getNext();
            count++;
        }
        ListNode currentNode = previousNode.getNext();
        nodeToInsert.setNext(currentNode);
        previousNode.setNext(nodeToInsert);
    }
    return headNode;
}

单向链表的删除

• 与插入类似

ListNode DeleteNodeFromLinkedList(ListNode headNode,int position){
    int size = ListLength(headNode);
    if(position > size | position < 1){
        System.out.println("删除位置错误！");
        return headNode;
    }
    if(position == 1){
        ListNode currentNode = headNode.getNext();
        return currentNode;
    }else{
        ListNode previousNode = headNode;
        int count = 1;
        while (count < position){
            previousNode = previousNode.getNext();
            count++;
        }
        ListNode currentNode = previousNode.getNext();
        previousNode.setNext(currentNode);
        currentNode = null;
    }
    return headNode;
}

删除单向链表

? 这个操作通过将当前结点存储在临时变量中然后释放当前结点（空间）的方式来完成。当释放完当前结点（空间）后，移动到下一个结点并将其存储在临时变量中，然后不断重复该过程直至释放所有结点。

void DeleteLinkedList(ListNode head){
    ListNode auxilaryNode,iterator = head;
    while (iterator != null){
        auxilaryNode = iterator.getNext();
        iterator = null;
        iterator = auxilaryNode;
    }
}

双向链表

双向链表的优点是：

• 对于链表中一个给定的结点，可以从两个方向进行操作。
• 在单向链表中，只有获得结点的前驱结点的指针，才能删除该结点。
• 然而，在双向链表中，即使没有一个结点的前驱结点的地址，也能删除该结点
• （因为每个结点有都一个指向前驱结点的指针，可以直接后退到前驱结点）。

双向链表主要的缺点是：

• 每个结点需再添加一个额外的指针，因此需要更多的空间开销。
• 结点的插入或删除更加费时（需要更多的指针操作）。

public class DLLNode {
    private int data;
    private DLLNode next;
    private DLLNode previous;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public DLLNode getNext() {
        return next;
    }

    public void setNext(DLLNode next) {
        this.next = next;
    }

    public DLLNode getPrevious() {
        return previous;
    }

    public void setPrevious(DLLNode previous) {
        this.previous = previous;
    }
}

双向链表的操作

• 插入操作
• 双向链表的删除

循环链表

• 在单向链表和双向链表中，都采用NULL.值表示链表的结束。然而，循环链表没有结束标志。
• 当遍历循环链表时需要特别小心，否则将会无限地遍历链表，因为在循环链表中每个结点都有一个后继结点。
• 注意，与单向链表不同，循环链表中没有next指针为NUL.L.的结点。循环链表在某些情况下是非常有用的。例如，当多个进程需要在相同的时间内使用同一个计算机资源（CPU）时，必须确保在所有其他进程使用这些资源完前，没有进程访问该资源（轮询算法）
• 在循环链表中，使用表头结点访问元素（与单向链表和双向链表中的表头结点相似）。

假设循环链表的类名为CLNode.循环列表的类结构可以为单向或者双向是一样的只是节点首尾相连

循环节点的操作

统计循环节点的个数

? 循环链表可以通过标记为表头的结点进行访问。为了统计结点个数，只能从标记为表头的结点开始遍历，利用虚拟结点--当前结点（current），当当前结点再次到达开始结点表头时结束计数过程。

? 如果链表为空，表头结点为NULL，在这种情况下设结点个数（count）等于0。否则，设置当前结点指向第一个结点（表头结点），然后遍历链表进行计数，直到当前结点达到开始结点。

    int CircularListLength(CLLNode headNode){
        int length =0;
        CLLNode currentNode - headNode;
        while (currentNode != null){
            length++;
            currentNode = currentNode.getNext();
            if(currentNode == headNode)
                break;
        }
        return length;
    }

输出循环链表的内容

? 假设循环链表可以通过表头结点进行访问。
? 由于所有的结点采用循环方式排列，所以链表的表头结点的前驱结点就是表尾结点。
? 假设要输出从表头结点开始的结点的内容。
? 输出结点内容，移动到下一个结点，继续输出直至再次到达表头结点。

在循环链表的表尾插入结点

在由表头开始的循环链表的表尾插入一个包含数据（data）的结点。
新结点将放在表尾结点（即循环链表的最后一个结点）的后面，也就是说，在表尾结点和第一个结点之间插人该新结点

在循环链表的表头插入结点

在循环链表的表头前插入结点与在表尾插入结点的唯一区别是，在插入新结点后，还需要更新指针。

其他操作

• 删除循环链表中的最后一个结点

  • 遍历循环链表，找到表尾结点及其前驱结点。
  • 更新表尾结点的前驱结点的next指针，使其指向表头结点。
  • 移除表尾结点。

• 删除循环链表中的第一个结点

循环链表的应用

循环链表可用于管理计算机的计算资源，还可用于实现栈和队列。

其他链表

一种存储高效的双向链表

• 在双向链表常规的实现中，需要一个指向后继结点的正向指针和一个措向前驱结点的反向指针。这表明双向链表中的结点由数据、一个指向后继结点的指针和一个指向前驱结点的指针构成。
• 而这种新的双向链表只需要一个指针即可

具体定义：

松散链表

• 与数组相比，链表的最大优势在于，在任何位置插入元素的时间开销仅为0（1）。然而，在链表中查找某个元素的时间开销则是0（n）。下面介绍一种单向链表的简单变种，称为松散链表。
• 松散链表中的每个结点存储多个元素（简称为块）。而每一块中的所有结点由循环链表链接在一起。

数据结构与算法-链表-未完

原文：https://www.cnblogs.com/shitouzi-shi/p/14383462.html