数据结构系列之一 链表、栈和队列

  • 2018-05-13
  • 189
  • 0

今天要说的这三种数据结构:链表、栈、队列,都是非常简单和基础的数据结构。在后续的文章中都可能会用到。所以,在这里,花很小的篇幅,简单的介绍下。

链表

链表是一种非常简单的数据结构。由一组元素以一个特定的顺序链接在一起,成为一个数据集它和数组非常相像,常常用来替代数组。

相比于数组,它的优点是,它比数组更适合频繁的插入和删除;缺点是,它不支持随机读。由于链表的每一个元素的空间是动态分配的。所以,在一些系统中数据集的大小或个数不确定的时候,链表的使用率会有很大的增加。

虽然说链表非常简单,也是个基础的东西,但不代表它没有用。在很多地方,链表都有使用,比如:在一些链式文件系统中,就用了链表的方式;Linux Kernel 的内存管理就用了链表和红黑树。

链表一般分为三种,但实现起来差不太多:

  1. 单向链表;元素之间通过一个指针链接,由前一个指向后一个,这种结构允许单向遍历。
  2. 双向链表;元素之间通过两个指针相连,对于某个元素,它既指向它后面的元素,也指向前面的元素,所以,它支持正向和反向两种方式遍历。
  3. 循环列表;链表的最后一个元素,指向链表的第一个元素,使链表成环。所以,允许循环遍历。

单向链表

单向链表是最容易的理解的。

center

链表中的每一个节点,都包含两个区域:数据域、指针域。数据域保存了节点真正要存放的数据。指针域则保存下一个节点的内存地址。当最后一个元素的时候,因为没有下一个元素了,则保存一个空指针,在C语言中,表示为 NULL

通过保存下一个元素的地址,单向链表完成了将元素串联起来的功能。

我们这里实现一个保存整形数据的链表,在实际的使用中,可以用任意其他的数据来替代这个整形。

代码实现如下:

typedef struct _list_node {
    int data;
    struct _list_node* next;
} Node;

Node* list_init(int v) {

    Node* head = NULL;
    head = (Node*)malloc(sizeof(Node));
    if (head == NULL) return head;

    head->data = v;
    head->next = NULL;
    return head;
}

int list_insert_next(Node* n, int v){

    if (n == NULL) return -1;

    Node* new_node = (Node*)malloc(sizeof(Node));
    if(new_node == NULL) return -1;

    new_node->data = v;
    new_node->next = n->next;
    n->next = new_node;

    return 0;
}

int list_delete_next(Node* n){

    if(n == NULL || n->next == NULL) return -1;

    Node* old_node = n->next;
    n->next = old_node->next;

    free(old_node);

    return 0;
}

void list_destory(Node* head) {

    while(head->next != NULL){

        Node* n = head->next;
        head->next = n->next;
        free(n);
    }

    free(head);
}

上面的代码写了一些常用的操作,插入、删除、销毁。

单链表反转

在面试中,链表中有一个题比较容易考,就是单链表的反转。单链表反转有很多方法,比如,通过一个栈来保存所有的节点地址,然后拿出来重新连接,就完成了反转;再比如,通过递归的方法,遍历整个链表,到了末尾的时候反转,利用调用栈保存节点地址来实现。

上面两种实现起来很简单,但方式略显麻烦。空间复杂度也有点高。最实用的方法是通过三个指针来进行反转。下面写出了这种方法的代码,适用于我们这里的链表形式。

Node* list_reverse(Node* head){

    if(head == NULL || head->next == NULL) return head;

    Node* n = head;
    Node* n1 = head;
    Node* tmp;

    while(n1 != NULL){

        tmp = n1->next;
        n1->next = n;
        n = n1;
        n1 = tmp;
    }
    head->next = NULL;
    return n;
}

双向链表

双向链表是在单向链表的基础上,增加了指向前一个节点的指针。其他相同。

循环链表

循环链表,将尾元素的next指针指向首元素,就形成了一个循环链表。其实本质上来说,这样已经没有一个首元素和尾元素之分了。但是为了更好的说明,还沿用这样的称呼。


栈是一种重要的数据结构,在计算机的各个系统中起着不可替代的作用。

栈是一种动态的数据集合,它并不限制存储的方式,我们可以用数组,也可以用链表。它规定了数据的存取方式。

为了实现栈的的特性 LIFO(Last In First Out),它规定了数据的存取方式:

  1. 数据只能在数据集尾部插入
  2. 数据只能在数据集尾部拿出

通过这两个规定,就可以让数据实现后进先出。最先进去的元素,最晚出来。

代码太过于简单,就不贴了。

队列

队列同栈一样,没有规定存储的数据结构,放入数据的方式也相同。

区别在于取出数据的方式: 队列需要在数据集的头部取出元素。

通过规定这两项规定,使得队列成为一个FIFO(Fisrt In First Out) 的数据结构。

最先进去的元素,总是最先出来。

结尾

简单介绍下这三种基础的数据结构,为以后高级的数据结构打基础。


作者和出处(reposkeeper) 授权分享 By CC BY-SA 4.0 Creative Commons License

关注微信公众号,获取新文章的推送!
qrcode

评论

还没有任何评论,你来说两句吧

发表评论

*

code