链式存储结构

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

有关术语

结点：数据元素的存储映像。由数据域和指针域两部分组成
- 数据域：存储元素数值数据
- 指针域：存储直接后继结点的存储位置
链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构
- 单链表
  - 结点只有一个指针域的链表，称为单链表或线性链表
- 双链表
  - 有两个指针域的链表，称为双链表
- 循环链表
  - 首尾相接的链表称为循环链表
头指针
- 指向链表中第一个结点的指针
首元结点
- 指链表中存储第一个数据元素a1的结点
头结点
- 在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
- 设置头结点的好处
  - 便于首元结点的处理
    - 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
  - 便于空表和非空表的统一处理
    - 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

链表的特点

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

链表的优缺点

优点
- 数据元素的个数可以自由扩充
- 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点
- 存储密度小
- 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）

顺序表和链表的比较

存储结构比较项目	顺序表	链表
存储空间	预先分配，会导致空间闲置或溢出现象	动态分配，不会出现存储空间闲置或溢出现象
存储密度	不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1	需要借助指针来体现元素间的逻辑关系，存储密度小于1
存取元素	随机存取，按位置访问元素的时间复杂度为O(1)	顺序存取，按位置访问元素时间复杂度为O(n)
插入、删除	平均移动约表中一半元素，时间复杂度为O(n)	不需移动元素，确定插入、删除位置后，时间复杂度为O(1)
适用情况	① 表长变化不大，且能事先确定变化的范围 ② 很少进行插入或删除操作，经常按元素位置序号访问数据元素	① 长度变化较大 ② 频繁进行插入或删除操作

C++代码实现

#include<iostream>
#include<stdlib.h>
using namespace std;

#define OVERFLOW -2
#define OK 1
#define ERROR -1

typedef int Status;
typedef int Elemtype;

/* typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode;

typedef struct{
    lnode *l;
}LinkList; */

typedef struct LNode {
    Elemtype data;
    struct LNode* next;
}LNode, * LinkList;


// 构造一个空的单链表
Status InitList(LinkList& L)
{
    L = new LNode; // 头指针L指向头结点
    if (!L) exit(OVERFLOW);
    L->next = NULL;  // 指针域置空
    return OK;
}

// 前插法创建单链表
void CreateList_H(LinkList& L, int n)
{
    LinkList p;
    int i;
    L = new LNode;  
    L->next = NULL;  // 先建立一个带头结点的空链表
    // for(i = 0; i < n; ++i)
    for (i = 1; i < n + 1; ++i)
    {
        cout << "请输入第" << i << "个结点的数据" << endl;
        p = new LNode;  // 生成新结点*p
        cin >> p->data;  // 输入元素赋值给新结点*p的数据域
        p->next = L->next;
        L->next = p; // 将新结点*p插入到头结点之后
    }
}


// 尾插法创建单链表
Status CreateList_L(LinkList& L, int n)
{
    LinkList r, p;
    int i;
    L = new LNode;
    L->next = NULL;
    // 尾结点指向头结点
    r = L;
    for (i = 1; i < n + 1; ++i)
    {
        cout << "请输入第" << i << "个结点的数据" << endl;
        p = new LNode;  // 生成新结点
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
    return OK;
}

// 取值
Status GetElem(LinkList L, int i, Elemtype& e)
{
    // 根据序号i获取元素的值，用e返回值
    int j;
    LinkList p;
    for (p = L->next, j = 1; j < i && p; j++)
        p = p->next;
    if (!p || j > i) return ERROR;
    e = p->data;
    return OK;
}

// 在链表中查找值为e的元素的位置，返回其地址
LinkList LocateElem_L(LinkList L, Elemtype e)
{
    LinkList p;
    p = L->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    return p;
}

// 插入
Status ListInsert(LinkList& L, int i, Elemtype& e)
{
    LinkList p, s;
    int j;
    for (p = L, j = 0;j < i - 1 && p; j++)
        p = p->next;
    if (!p || j > i) return ERROR;
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

// 删除
Status ListDelete(LinkList& L, int i, Elemtype& e)
{
    LinkList p, q;
    int j;
    for (p = L, j = 0;j < i - 1 && p; j++)
        p = p->next; 
    if (!p || j > i) return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    return OK;
}

// 销毁
Status DestroyList(LinkList& L)
{
    LinkList p;
    while (L)
    {
        p = L;
        L = L->next;
        delete p;
    }
    return OK;
}

// 清空
Status ClearList(LinkList& L)
{
    LinkList p, q;
    p = L->next; // p指向第一个结点
    while (p)  // 没到表尾
    {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;  // 头结点指针域为空
    return OK;
}

// 求表长
int ListLength_L(LinkList L){
    // 返回L中数据元素的个数
    int i;
    LinkList p;
    p = L->next;  // p指向第一个结点
    i = 0;
    while (p)  // 遍历单链表，统计结点数
    {
        i++;
        p = p->next;
    }
    return i;
}

// 判断表是否为空
int ListEmpty(LinkList L) {
    // 若L为空，返回1；否则，返回0
    if (L->next)
        return 0;
    else
        return 1;
}

int main()
{
    LinkList L;
    Elemtype e;
    int i, n;

    // 创建链表测试
    cout << "请输入表长：";
    cin >> n;
    // 尾插法创建
    CreateList_L(L, n);

    cout << "表长为：";
    cout << ListLength_L(L) << endl;

    // 查找测试
    cout << "请输入您需要查找元素的位置：";
    cin >> i;
    GetElem(L, i, e);
    cout << e;

    // 删除测试
    cout << "请输入您要删除的元素的位置：";
    cin >> i;
    ListDelete(L, i, e);
    cout << e;

    return 0;
}

Python代码实现

SingleNode

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2019-10-02 09:32:38
# @Author  : Your Name (you@example.org)
# @Link    : http://example.org
# @Version : $Id$

class SingleNode(object):
    def __init__(self, item):
        self.item = item
        self.next = None

class SingleLinkList(object):
    def __init__(self):
        self._head = None

    def isEmpty(self):
        return self._head == None

    def length(self):
        cur = self._head

        count = 0

        while cur:
            count += 1
            cur = cur.next

        return count

    def travel(self):
        cur = self._head

        while cur:
            print(cur.item, end=" ")
            cur = cur.next
        print()
        return None

    def addFirst(self, item):
        node = SingleNode(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        node = SingleNode(item)
        
        if self.isEmpty():
            self._head = node

        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        if pos <= 0:
            self.addFirst(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = SingleNode(item)
            count = 0
            pre = self._head
            # 数据从0开始
            # 从1开始 应该为 pos - 2
            while count < (pos - 1):
                count += 1
                pre = pre.next

            node.next = pre.next
            pre.next = node

    def remove(self, item):
        cur = self._head
        pre = None

        while cur:
            if cur.item == item:
                if not pre:
                    self._head = cur.next
                else:
                    pre.next = cur.next

                break

            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        cur = self._head
        while cur:
            if cur.item == item:
                return True
            cur = cur.next
        return False


if __name__ == '__main__':
    sll = SingleLinkList()
    sll.addFirst(10)
    sll.addFirst(20)
    sll.append(30)
    sll.travel()
    sll.remove(10)
    sll.travel()
    print(sll.search(30))
    print(sll.search(10))
    sll.insert(2, 40)
    sll.travel()
    print(sll.length())
    print(sll.isEmpty())
    sll.insert(2, 50)
    sll.travel()

20 10 30 
20 30 
True
False
20 30 40 
3
False
20 30 50 40 
[Finished in 0.6s]

SingleCycLinkedList

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2019-10-02 11:13:14
# @Author  : Your Name (you@example.org)
# @Link    : http://example.org
# @Version : $Id$

class SingleNode(object):
    def __init__(self, item):
        self.item = item
        self._head = None

class SingleCysLinkedList(object):
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head == None

    def length(self):
        if self.is_empty():
            return 0
        count = 1
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        if self.is_empty():
            return
        cur = self._head
        print(cur.item, end=" ")

        while cur.next != self._head:
            cur = cur.next
            print(cur.item, end=" ")
        print()

    def addFirst(self, item):
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            node.next = self._head
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            self._head = node

    def append(self, item):
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            node.next = self._head
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            node.next = self._head

    def insert(self, pos, item):
        if pos<= 0:
            self.addFirst(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = SingleNode(item)
            cur = self._head
            count = 0
            while count < (pos - 1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        if self.is_empty():
            return
        cur = self._head
        pre = None
        if cur.item == item:
            # 删除第一个元素
            if cur.next != self._head:
                while cur.next != self._head:
                    cur = cur.next
                cur.next = self._head.next
                self._head = self._head.next
            else:
                # 只有一个元素
                self._head = None

        else:
            pre = self._head
            while cur.next != self._head:
                if cur.item == item:
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            if cur.item == item:
                pre.next = cur.next

    def search(self, item):
        if self.is_empty():
            return False
        cur = self._head
        if cur.item == item:
            return True
        while cur.next != self._head:
            cur = cur.next
            if cur.item == item:
                return True
        return False    

if __name__ == '__main__':
    ll = SingleCysLinkedList()
    ll.addFirst(1)
    ll.addFirst(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print("length: {0}".format(ll.length()))
    ll.travel()
    print(ll.search(3))
    print(ll.search(7))
    ll.remove(1)
    print("length:", ll.length())
    ll.travel()

length: 6
6 2 1 4 3 5 
True
False
length: 5
6 2 4 3 5 
[Finished in 0.4s]

DLinkList

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2019-10-02 12:10:18
# @Author  : Your Name (you@example.org)
# @Link    : http://example.org
# @Version : $Id$

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None

class DLinkList(object):
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head == None

    def length(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        cur = self._head
        while cur:
            print(cur.item, end=" ")
            cur = cur.next
        print()

    def add(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            node.next = self._head
            self._head.prev = node
            self._head = node

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def search(self, item):
        cur = self._head
        while cur:
            if cur.item == item:
                return True
            cur = cur.next
        return False

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos - 1):
                count += 1
                cur = cur.next
            # 将node的prev指向cur
            node.prev = cur
            # 将node的next指向cur的下一个结点
            node.next = cur.next
            # 将cur的下一个结点的prev指向node
            cur.next.prev = node
            # 将cur的next指向node
            cur.next = node

    def remove(self, item):
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                if cur.next == None:
                    self._head = None
            else:
                cur.next.prev = None
                self._head = cur.next
            return

        while cur:
            if cur.item == itme:
                cur.prev.next = cur.next
                cur.next.prev = cur.prev
                break

            cur = cur.next

if __name__ == '__main__':
    ll = DLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print("length:", ll.length())
    ll.travel()
    print(ll.search(3))
    print(ll.search(4))
    ll.remove(1)
    print("length: {}".format(ll.length()))
    ll.travel()

length: 6
6 2 1 4 3 5 
True
True
length: 5
2 1 4 3 5 
[Finished in 0.1s]

数据结构——链表

链式存储结构

有关术语

链表的特点

链表的优缺点

顺序表和链表的比较

C++代码实现

Python代码实现

SingleNode

SingleCycLinkedList

DLinkList

热门文章

最新文章

相关课程

相关电子书