线性表 ： 零个或多个元素的有限序列

抽象数据类型定义

ADT 线性表 (List)
Data
    线性表的数据对象集合为 {a1, a2, ..., an}，每个元素类型均为 DataType。其中，除第一个元素外，每个元素有且只有一个直接前驱元素。除了最后一个元素外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一关系。
Operation
    InitList(*L) : 初始化操作，建立一个空的线性表 L
    ListEmpty(L) : 若线性表为空，返回 true，否则返回 false
    ClearList(*L) : 将线性表清空
    GetElem(L, i, *e) : 将线性表 L 中的第 i 个元素值返回给 e
    LocateElem(L, e) : 在线性表中查找给定元素，如果查找成功，返回该元素在表中序列号。否则，返回 -1 表示失败
    ListInsert(*L, i, e) : 在线性表中的第 i 个位置插入新元素 e
    ListDelete(*L, i, *e) : 删除线性表 L 中的第 i 个位置元素，并用 e 返回其值
    ListLength(L) : 返回线性表 L 的元素个数
endADT

线性表的顺序储存结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

结构定义

type int TYPE
var MAXSIZE int = 10


type List struct {
    Data [MAXSIZE]TYPE
    Length int
}

顺序储存结构的插入与删除

插入


func (list *List) ListInsert(i int, e TYPE) error {
    if i < 0 || i > MAXSIZE - 1 || list.Length - 1 < i  {
        return errors.New("错误")
    } else {
         // 插入点的数据依次向后移动
        for j := list.Length - 1; j >= i; j -- {
            list.Data[j + 1] = list.Data[j]
        }
    }
    list.Data[i] = e
    list.Length += 1
    return nil
}

删除

func (list *LIst) ListDelete(i int, e *TYPE) error {
    if list.Length == 0 || i < 0 || i >list.Length {
        return errors.New("错误")
    } else if i < list.Length {
        *e = list.Data[i]
        // 删除点的元素依次向前移动
        for int j := i;  j < list.Length - 1; j ++ {
            list.Data[j] = list.Data[j + 1]
        }
    }
    list.Length -= 1
    return nil
}

优缺点

优点 : 无需为表示表中元素之间的逻辑关系而增加额外的空间。可以快速地存取表中任意位置的元素
缺点 : 插入和删除操作需要移动大量元素。当线性表长度变化较大时，难以确定存储空间的容量。造成存储空间的“碎片”。

线性表的链式储存结构

n 个节点链结成一个链表，即为线性表的链式存储结构。

    type LinkedList struct {
        Data TYPE
        Next *LinkedList
    }

单链表的插入与删除

插入

func (list *LinkedList) ListInsert(i int, e TYPE) error {
    int foo := 0
    for list != nil && foo < i {
        list = list.Next
        foo += 1
    }
    if list == nil || foo > i {
        return errors.New("错误")
    }
    node = LinkedList{Data : e, Next : nil}
    // 将插入元素的 Next 指向当前节点的下一个节点
    node.Next = list.Next
    // 当前节点的 Next 为被插入元素
    list.Next = node
    return nil
}

删除

func (list *LinkedList) ListDelete(i int, e *TYPE) error {
     int foo := 0
    for list != nil && foo < i {
        list = list.Next
        foo += 1
    }
    if list == nil || foo > i {
        return errors.New("错误")
    }
    *e = list.Next.Data
    // 当前节点的 Next 指向下一个节点的 Next
    // 等待 gc 自动回收
    list.Next = list.Next.Next
    return nil
}

单链表结构与顺序储存结构优缺点

储存分配方式 ：

  • 顺序储存结构用一段连续的存储单元依次存储线性表的数据元素。
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。
    时间性能 ：
  • 查找
    • 顺序储存结构 O(1)
    • 单链表 O(n)
  • 插入与删除
    • 顺序存储结构需要平均移动表长一半的元素，时间为 O(n)
    • 单链表在找出某位置的指针后，插入和删除时间仅为 O(1)
  • 空间性能
    • 顺序存储结构需要预分配存储空间，分大了，浪费，分小了容易发生上溢。
    • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

当线性表中元素个数变化较大或者根本不知道有多大时，最好用单链表结构。而如果事先知道线性表的大致长度，用顺序结构效率会高