单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适合解决哪种问题呢？
从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
举个删除的例子：
删除结点中“值等于某个给定值”的结点：
对于这种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。
尽管单纯的删除操作时间复杂度是O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为O(n)。
删除给定指针指向的结点：
对于第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p -> next = q，说明 p 是 q 的前驱结点。
但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！
同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。
除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。
如果你熟悉Java语言，你肯定用过LinkedHashMap这个容器。如果你深入研究LinkedHashMap的实现原理，就会发现其中就用到了双向链表这种数据结构。
实际上，这里有一个更加重要的知识点需要你掌握，那就是用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
1.3、栈从栈的操作特性上来看， 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。先进后出。
/** * @author xiandongxie * 基于数组实现的栈 */ public class ArrayStack { public String[] arr = null; private int num;//栈中元素个数 private int n;// 栈的大小 public ArrayStack(int n) { arr = new String[n]; num = 0; this.n = n; } public boolean push(String value) { if (StringUtils.isEmpty(value)) return false; if (num >= n) return false; arr[num] = value; num++; return true; } public String pop() { if (num > n || num <= 0) return null; num--; return arr[num]; } } 1.4、队列队列跟栈一样，也是一种操作受限的线性表数据结构。只不过可以再两端操作，先进先出。
1、单列队列队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、 Linux 环形缓存，都用到了循环并发队列； Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
/** * 用数组实现队列 */ class ArrayQueue { // 装载数据的数组 private String[] arr; // 数组容量大小 private int n; // 队列头 private int start; // 队列尾 private int end; public ArrayQueue(int n) { this.arr = new String[n]; this.start = 0; this.end = 0; this.n = n; } // 添加元素 public boolean push(String data) throws Exception { if (end >= n && start == 0) { throw new Exception("超出容量，且数据不需要移动，此时只能对队列扩容才能存入，" + "end=" + end + ", n=" + n + ", start=" + start); } if (end >= n && start > 0) { System.out.println("超出容量，但是队列头部已经消费，可以移动数据扩容，" + "end=" + end + ", n=" + n + ", start=" + start); for (int i = 0; i < end - start; i++) { arr[i] = arr[start + i]; } end = end - start; start = 0; } arr[end] = data; end++; return true; } // 取出元素 public String pop() throws Exception { if (end <= 0 || start >= end) { throw new Exception("没有元素，队列为空，end=" + end + ", n=" + n + ", start=" + start); } String value = arr[start]; start++; return value; } public String[] getArr() { return arr; } } /** * 用链表实现队列 */ class LinkedQueue { // 定义节点类 private class Node { Node nextNode; String value; } // 头指针 private Node head; // 尾指针 private Node tail; // 数据个数 private int size; public LinkedQueue() { this.size = 0; } // 添加 public boolean push(String data) { Node newNode = new Node(); newNode.value = data; if (size == 0) { head = newNode; } else { tail.nextNode = newNode; } tail = newNode; size++; return true; } // 移除 public String pop() throws Exception { if (size <= 0) { throw new Exception("队列为空，size=" + size); } if (size == 1){ tail = null; } size--; String value = head.value; head = head.nextNode; return value; } }
对于栈来说，我们只需要一个栈顶指针就可以了。
但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。
你可以结合下面这幅图来理解。当 a 、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置， tail 指针指向下标为 4 的位置。