一个线性表有n个元素（n<MAXSIZE, MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。

在顺序存储（数组）中实现：

def insertInArray(linearList, x):
    n = len(linearList)
    if n < MAXSIZE:
        for i in range(n):  # 查找插入位置
            if linearList[i] > x:
                break
        linearList.insert(i, x)  # 在找到的位置插入x
    else:
        print("数组已满，无法插入")

# 示例：
linearList = [1, 2, 4, 6]
x = 3
insertInArray(linearList, x)  # 输出：[1, 2, 3, 4, 6]

在链式存储（单链表）中实现：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_sorted(self, x):
        new_node = Node(x)
        if not self.head or new_node.data <= self.head.data:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            while current.next and current.next.data < x:
                current = current.next
            new_node.next = current.next
            current.next = new_node

# 示例：
linked_list = LinkedList()
linked_list.insert_sorted(3)  # 添加元素3

比较优劣：

- **顺序存储**：
- 优势：空间利用率高，因为元素存储在连续的内存块中，不需要额外节点指向，适合插入位置已知的情况。
- 劣势：插入和删除操作（尤其是中间位置）代价较高，需要移动大量的元素。

- **链式存储**：
- 优势：插入和删除操作快（时间复杂度一般为O(1)），因为只需要修改节点的连接即可，无需移动其他元素。
- 劣势：空间开销大，每个元素都需要一个单独的节点，而且查找某个特定值可能较慢（平均或最坏情况下的时间复杂度为O(n)）。