复杂链表的复制-图解数据结构之数组、链表、栈、队列

今天带各位回顾一下线性数据结构：数组、链表、栈、队列，相信通过下面的文字，你会加深对这几种数据结构的认识。一 数组

  数组（Array）是一种很常见的数据结构。它是由相同类型的元素（）的集合所组成，并且被分配一块连续的内存来存储（与链表对比）。利用元素的索引（index）可以计算出该元素对应的存储地址。它的特点是提供随机访问并且容量有限。

假如数组的长度为 n。
访问：O（1）//访问特定位置的元素   
插入：O（n ）//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除：O（n）//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

  数组二 链表2.1 链表简介

  链表（）虽然是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针()。由于不必须按顺序存储，链表在插入和删除的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是O(logn) 和O(1)。

  使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。链表不具有数组随机读取的优点，但是插入删除元素的时间复杂度为O(1)

  2.2 链表分类

  常见链表分类：

  单链表

  双向链表

  循环链表

  双向循环链表

假如链表中有n个元素。
访问：O（n）//访问特定位置的元素
插入删除：O（1）//必须要要知道插入元素的位置

  2.2.1 单链表

  单链表单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向null。

  单链表2.2.2 循环链表

  循环链表其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向null，而是指向链表的头结点。

  循环链表2.2.3 双向链表

  双向链表包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。

  双向链表2.2.4 双向循环链表

  双向循环链表最后一个节点的 next 指向head，而 head 的prev指向最后一个节点，构成一个环。

  双向循环链表2.3 数组vs链表

  数组使用的是连续内存空间对CPU的缓存机制友好，链表则相反。

  数组的大小固定，声明之后就要占用所需的连续内存空间。如果声明的数组过小的话，需要再申请一个更大的内存空间，然后将原数组拷贝进去。数组多的情况下，这将是非常耗时的。链表则天然支持动态扩容。

  三 栈3.1 栈简介

  栈(stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照后进先出（LIFO, Last In First Out）的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。栈常用一维数组或链表来实现，用数组实现的队列叫作顺序栈，用链表实现的队列叫作链式栈。

假设堆栈中有n个元素。
访问：O（n）//最坏情况 
插入删除：O（1）//顶端插入和删除元素

  栈3.2 栈的常见应用常见应用场景3.2.1 实现浏览器的回退和前进功能

  我们只需要使用两个栈(Stack1和Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看2这个页面的时候，你点击回退按钮，我们依次把4,3这两个页面从Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面3，你点击前进按钮，我们将3页面从Stack2 弹出，然后压入到 Stack1 中。示例图如下:

  栈实现浏览器倒退和前进3.2.2 检查符号是否成对出现

  给定一个只包括'('，')'，'{'，'}'，'['复杂链表的复制，']'的字符串，判断该字符串是否有效。

  有效字符串需满足：

  左括号必须用相同类型的右括号闭合。

  左括号必须以正确的顺序闭合。

  比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]" 、"([)]" 则不是。

  这个问题实际是的一道题目复杂链表的复制，我们可以利用栈Stack来解决这个问题。

  首先我们将括号间的对应规则存放在Map中，这一点应该毋容置疑；

  创建一个栈。遍历字符串，如果字符是左括号就直接加入stack中，否则将stack的栈顶元素与这个括号做比较，如果不相等就直接返回false。遍历结束，如果stack为空，返回true。

public boolean isValid(String s){
    // 括号之间的对应规则
    HashMap mappings = new HashMap();
    mappings.put(')', '(');
    mappings.put('}', '{');
    mappings.put(']', '[');
    Stack stack = new Stack();
    char[] chars = s.toCharArray();
    for (int i = 0; i 
[1]: https://xuan.ddwoo.top/index.php/archives/559/
[2]: https://xuan.ddwoo.top/index.php/archives/560/
[3]: https://xuan.ddwoo.top/index.php/archives/559/
[4]: https://xuan.ddwoo.top/index.php/archives/562/                
        本文共 1423 个字数,平均阅读时长 ≈ 4分钟