十年JAVA搬砖路——数据结构线性结构

谁借莪１个温暖的怀抱￠ 2023-10-15 09:44 109阅读 0赞

### 线性结构 ###

**线性表是一种数据结构**，用于存储一组有序的数据元素。它的特点是数据元素之间存在一对一的关系，每个元素只有一个前驱和一个后继（除了第一个元素和最后一个元素）。线性表可以用数组或链表来实现。

**数据是指事物的符号表示**，可以是数字、字符、图像、声音等。数据可以通过线性表来组织和存储，以便进行操作和处理。线性表提供了一种简单而有效的方式来管理和访问数据，使得数据的存储和检索变得更加方便和高效。

**线性表可以通过多种方式实现，其中最常见的两种方式是使用数组（顺序存储）和使用链表（链式存储）。**

\*\*1. 顺序存储：\*\*线性表的顺序存储是通过数组来实现的。数组将元素按照顺序连续存储在内存中，每个元素占据固定大小的内存空间。顺序存储的优点是可以通过索引直接访问元素，访问速度快。但是插入和删除操作需要移动元素，效率较低。

**2. 链式存储**：线性表的链式存储是通过链表来实现的。链表由节点（Node）组成，每个节点包含数据和指向下一个节点的指针（或引用）。节点在内存中可以非连续存储，通过指针将它们连接起来。链式存储的优点是插入和删除操作只需要修改指针的指向，效率较高。但是链式存储不支持随机访问，需要从头节点开始遍历到目标位置才能访问元素。

顺序存储 数组的基本操作：

1.  插入操作：在顺序存储结构中插入一个新元素，需要将插入位置之后的所有元素后移一位，然后将新元素放入指定位置。
2.  删除操作：从顺序存储结构中删除一个元素，需要将删除位置之后的所有元素前移一位，覆盖被删除的元素。
3.  访问操作：通过索引访问顺序存储结构中的元素，可以直接通过索引值来访问对应位置的元素。
4.  查找操作：在顺序存储结构中查找指定元素，需要遍历整个存储结构，逐个比较元素的值，直到找到目标元素或者遍历结束。
5.  更新操作：通过索引定位到顺序存储结构中的某个元素，然后修改该元素的值。

**• 线单向性链表常见的操作包括：**

1.  插入操作：
    
     *  头部插入：创建一个新节点，设置其数据值，并使其指针指向当前的第一个节点。更新头指针指向新节点。
     *  尾部插入：创建一个新节点，设置其数据值，并使其指针指向 null。更新最后一个节点的指针指向新节点。
     *  指定位置插入：定位到指定位置，创建一个新节点，设置其数据值，并使其指针指向该位置的下一个节点。更新前一个节点的指针指向新节点。
2.  删除操作：
    
     *  删除第一个节点：更新头指针指向第二个节点，并从链表中移除第一个节点。
     *  删除最后一个节点：遍历链表找到倒数第二个节点，并将其指针指向 null。
     *  删除指定节点：定位到要删除的节点，更新前一个节点的指针以跳过要删除的节点，并从链表中移除该节点。
3.  遍历操作：
    
     *  从头节点开始，通过跟随指针的指向依次遍历每个节点，直到到达链表的末尾。对每个节点执行所需的操作。
4.  搜索操作：
    
     *  从头节点开始，遍历链表并将每个节点的数据值与目标值进行比较。返回找到的节点或指示元素未找到。

**• 线单循环链表操作：**

插入操作：  
头部插入数据：

1.  创建一个新节点并设置其数据。
2.  如果列表为空（head 为空），将新节点的下一个指针设置为自身，并将 head 指针更新到新节点。
3.  如果列表不为空，请将新节点的下一个指针设置为当前头节点。
4.  遍历列表以查找最后一个节点（下一个指针指向当前头节点的节点）。
5.  更新最后一个节点的下一个指针以指向新的头节点。
6.  更新指向新节点的头部指针。  
    中间或者尾部插入数据：
7.  使用要插入的数据创建一个新节点。
8.  遍历链表，直到到达所需位置的节点。还要跟踪上一个节点。
9.  设置新节点的下一个指针到上一个节点的下一个节点。
10. 设置上一个节点的下一个指针到新节点。
11. 如果所需位置位于链表的末尾（即最后一个节点），请更新新节点的下一个指针以指向头节点。

删除操作

1.  通过遍历链表并跟踪上一个节点来查找要删除的节点。
2.  更新上一个节点的下一个指针，跳过要删除的节点，指向下一个节点。
3.  如果要删除的节点是头节点，请更新头指针以指向下一个节点。
4.  如果要删除的节点是最后一个节点，请更新上一个节点的下一个指针以指向头节点。  
    遍历操作/搜索操作  
    若要遍历单循环链表，可以从头节点开始并继续遍历，直到再次到达头节点。由于它是一个循环链表，因此您需要通过检查是否再  
    次到达头节点来确保不会陷入无限循环。

**• 双向链表操作：**  
插入操作

1.  创建一个新的节点，并将要插入的值存储在该节点中。
2.  如果链表为空，则将新节点设置为链表的头节点。
3.  如果要插入的位置是链表的头部，则将新节点插入到链表的头部，并将原来的头节点设置为新节点的后继节点。既新节点的后续节点指向原来的头结点，原来头节点的前驱节点指向新节点。
4.  如果要插入的位置不是链表的头部，则需要遍历链表找到要插入位置的前一个节点。
5.  将新节点的后继节点设置为前一个节点的后继节点，并将新节点的前驱节点设置为前一个节点。
6.  将前一个节点的后继节点设置为新节点，并将新节点设置为后继节点的前驱节点。

删除操作

1.  如果链表为空，则无法进行删除操作。
2.  如果要删除的位置是链表的头部，则将头节点的后继节点设置为新的头节点，并将新的头节点的前驱节点设置为None。
3.  如果要删除的位置不是链表的头部，则需要遍历链表找到要删除位置的节点。
4.  将要删除节点的前驱节点的后继节点设置为要删除节点的后继节点。
5.  如果要删除节点的后继节点不为空，则将要删除节点的后继节点的前驱节点设置为要删除节点的前驱节点