什么是线性表

前言

1、同一个问题可以有不同的表示（存储）方法
2、有一类共性问题：有序线性序列的组织和管理

定义（仅供理解）

定义一：线性表(Linear List)：由同类型数据元素构成有序序列的线性结构

定义二：线性表(Linear List):是一种基本的数据结构，用于存储一组有序的元素。线性表中的元素具有线性关系，即每个元素都有唯一的前驱和后继（除了第一个元素没有前驱和最后一个元素没有后继）。线性表可以通过顺序存储（数组）或链式存储（链表）来实现。

---

线性表初识

• 表中元素个数称为线性表的长度;
• 线性表没有元素时，称为空表;
• 表起始位置称表头，表结束位置称表尾;

线性表的特点

• 有序性：元素按线性顺序排列。
• 唯一性：每个元素都有唯一的前驱和后继。
• 动态性：元素的个数可以动态变化。

线性表的抽象数据类型描述

• 类型名称：线性表（List）
• 数据对象集：线性表是 **n (≥0)**个元素构成的有序序列 ( a1, a2, ...,an )
• 操作集：线性表L ∈ List，整数i表示位置，元素X ∈ ElementType，线性表基本操作主要有：

线性表的方法

1. 插入（Insert）：在指定位置插入一个新元素；
2. 删除（Delete）：删除指定位置的元素；
3. 查找（Find）：查找指定元素的位置；
4. 访问（Access）：访问指定位置的元素；
5. 更新（Update）：更新指定位置的元素；
6. 长度（Length）：获取线性表的长度。

线性表的实现

线性表可以通过顺序存储结构（数组）和链式存储结构（链表）来实现。

顺序存储结构（数组）github (opens new window)

顺序存储结构使用一段连续的存储单元来存储线性表中的元素。数组是一种典型的顺序存储结构。

class ArrayList {
    constructor() {
        this.data = [];
    }

    // 获取元素个数
    size() {
        return this.data.length;
    }

    // 获取指定位置的元素
    get(index) {
        if (index < 0 || index >= this.size()) {
            throw new Error("Index out of bounds");
        }
        return this.data[index];
    }

    // 在指定位置插入元素
    insert(index, element) {
        if (index < 0 || index > this.size()) {
            throw new Error("Index out of bounds");
        }
        this.data.splice(index, 0, element);
    }

    // 删除指定位置的元素
    remove(index) {
        if (index < 0 || index >= this.size()) {
            throw new Error("Index out of bounds");
        }
        return this.data.splice(index, 1)[0];
    }

    // 输出所有元素
    print() {
        console.log(this.data.toString());
    }
}

// 使用示例
const list = new ArrayList();
list.insert(0, 'A'); // 插入元素 A 到位置 0
list.insert(1, 'B'); // 插入元素 B 到位置 1
list.insert(2, 'C'); // 插入元素 C 到位置 2
list.print(); // 输出：A,B,C

console.log(list.get(1)); // 获取位置 1 的元素，输出：B

list.remove(1); // 删除位置 1 的元素
list.print(); // 输出：A,C

链表github (opens new window)

链表是一种使用节点和指针来实现的线性表，优点是插入和删除操作非常高效，缺点是访问任意位置的元素需要遍历链表。

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }

    // 获取元素个数
    getSize() {
        return this.size;
    }

    // 在链表末尾添加元素
    append(element) {
        const newNode = new Node(element);
        if (this.head === null) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }

    // 在指定位置插入元素
    insert(index, element) {
        if (index < 0 || index > this.size) {
            throw new Error("Index out of bounds");
        }
        const newNode = new Node(element);
        if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let current = this.head;
            let previous = null;
            let currentIndex = 0;
            while (currentIndex < index) {
                previous = current;
                current = current.next;
                currentIndex++;
            }
            newNode.next = current;
            previous.next = newNode;
        }
        this.size++;
    }

    // 删除指定位置的元素
    remove(index) {
        if (index < 0 || index >= this.size) {
            throw new Error("Index out of bounds");
        }
        let current = this.head;
        if (index === 0) {
            this.head = current.next;
        } else {
            let previous = null;
            let currentIndex = 0;
            while (currentIndex < index) {
                previous = current;
                current = current.next;
                currentIndex++;
            }
            previous.next = current.next;
        }
        this.size--;
        return current.element;
    }

    // 输出所有元素
    print() {
        let current = this.head;
        let result = [];
        while (current !== null) {
            result.push(current.element);
            current = current.next;
        }
        console.log(result.toString());
    }
}

// 使用示例
const linkedList = new LinkedList();
linkedList.append('A'); // 添加元素 A
linkedList.append('B'); // 添加元素 B
linkedList.append('C'); // 添加元素 C
linkedList.print(); // 输出：A,B,C

linkedList.insert(1, 'D'); // 在位置 1 插入元素 D
linkedList.print(); // 输出：A,D,B,C

linkedList.remove(2); // 删除位置 2 的元素
linkedList.print(); // 输出：A,D,C

总结

线性表是一种基本而重要的数据结构，广泛应用于各种算法和数据处理场景。顺序表和链表是两种主要的实现方式，各有优缺点，选择合适的实现方式取决于具体的应用场景和需求。

线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。

• 插入、删除不需要移动数据元素，只需要修改“链”。

多重链表

定义及属性 多重链表：链表中的节点可能同时隶属于多个链

• 多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；
• 但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表。

多重链表有广泛的用途： 基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。