线性结构 数组与链表
线性结构
线性数据结构有两端，有时被称为左右，某些情况被称为前后。你也可以称为顶部和底部，名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式，特别是添加和移除项的位置。例如一些结构允许从一端添加项，另一些允许从另一端移除项。
数组或列表
数组(Array)是编程界最常见的数据结构，有些编程语言被称作位列表(List)。几乎所有编程语言都原生内置数组类型，只是形式向略有不同，因为数组是最简单的内存数据结构。
数组的定义是：一个存储元素的线性集合(Collection)，元素可以通过索引(Index)来任意存取，索引通常是数字，用来计算元素之间存储位置的偏移量。
链表
数组的缺点：要存储多个元素，数组(或列表)可能是最常见的数据结构。但是数组不总是组织数据的最佳结构。在大多数编程语言中，数组的大小是固定的，所以当数组被填满时，再要加入新的元素会非常困难。并且从数组起点或中间插入或移除元素的成本很高，因为需要将数组中的其他元素向前后平移。
**链表(Linked list)中的元素在内存中不是连续存放的。链表是由一组节点(Node)**组成的集合，每个节点由元素本身和一个指向下一个元素的引用(也被称作链接或指针)组成。相对于数组，链表的好处在于，添加或移除元素的时候不需要移动其他元素。
链表的种类
单向链表(Singly linked list)：是最基本的链表，每个节点一个引用，指向下一个节点。单向链表的第一个节点称为头节点(head node)，最后一个节点称为尾节点(tail node)，尾节点的引用为空（None），不指向下一个节点。
**双向链表(Doubly linked list)**和单向链表的区别在于，在链表中的节点引用是双向的，一个指向下一个元素，一个指向上一个元素。
**循环链表(Circular linked list)**和单向链表类似，节点类型都一样。唯一的区别是 ，链表的尾节点引用指向头节点。
双向循环链表：类似于双向链表，尾节点的后置引用指向头节点，头节点的前置引用指向尾节点。
单向链表的操作
| 方法 | 操作 |
|---|---|
| append | 向链表尾部添加一个元素 |
| insert | 在链表的指定位置插入一个元素 |
| pop | 从链表特定位置删除并返回元素 |
| remove | 从链表中删除给定的元素 |
| find | 返回元素的索引 |
| iter | 迭代链表元素 |
| size | 获取链表大小 |
| clear | 清空链表 |
Python实现单向链表
# python3class Node: def __init__(self, value=None, next=None): self.value = value self.next = nextclass LinkedList: def __init__(self): self.head = None self.tail = None self.size = 0 def append(self, value): node = Node(value) if self.head is None: self.head = node self.tail = node else: self.tail.next = node self.tail = node self.size += 1 def insert(self, index, value): if 0 <= index <= self.size: node = Node(value) current = self.head previous = Node(next=current) count = 0 while count < index: previous = current current = current.next count += 1 previous.next = node node.next = current if previous.value is None: self.head = node if node.next is None: self.tail = node self.size += 1 return True else: return False def pop(self, index): if 0 <= index <= self.size and self.head is not None: current = self.head previous = Node(next=current) count = 0 while count < index: previous = current current = current.next count += 1 previous.next = current.next if previous.value is None: self.head = current.next if current.next is None: self.tail = previous self.size -= 1 return current.value else: return None def remove(self, item): found = False current = self.head previous = Node(next=current) index = 0 while not found and current is not None: if current.value == item: found = True else: previous = current current = current.next index += 1 if found: previous.next = current.next if previous.value is None: self.head = current.next if current.next is None: self.tail = previous self.size -= 1 return index else: return -1 def find(self, item): current = self.head count = 0 while current is not None: if current.value == item: return count else: current = current.next count += 1 return -1 def iter(self): current = self.head while current is not None: yield current.value current = current.next def size(self): return self.size def clear(self): self.head = None self.tail = None self.size = 0 def is_empty(self): return self.size == 0 def __len__(self): return self.size() def __iter__(self): iter self.iter() def __getitem__(self, index): return self.find(index) def __contains__(self, item): return self.find(item) != -1复制代码
JavaScript实现单向链表
// ES6class Node { constructor(value=null, next=null) { this.value = value; this.next = next; }}class LinkedList { constructor() { this.head = null; this.tail = null; this.size = 0; } append(value) { let node = new Node(value); if (this.head === null) { this.head = node; this.tail = node; } else { this.tail.next = temp; this.tail = temp; } this.size += 1; } insert(index, value) { if (0 <= index <= this.size) { let node = new Node(value); let current = this.head; let previous = new Node(next=current); let count = 0; while (count < index) { previous = current; current = current.next; count += 1; } previous.next = node node.next = current if (previous.value === null) { this.head = node; } if (node.next === null) { this.tail = node; } this.size += 1 return true; } else { return false; } } pop(index) { if (0 <= index <= self.size && this.head === null) { let current = this.head; let previous = new Node(next=current); let count = 0; while (count < index) { previous = current; current = current.next; count += 1; } previous.next = current.next; if (previous.value === null) { this.head = current.next; } if (current.next === null) { this.tail = previous; } this.size -= 1; return current.value; } else { return null; } } remove(item) { let found = false; let current = this.head; let previous = new Node(next=current); let index = 0; while (! found && current !== null) { if (current.value === item) { found = true; } else { previous = current; current = current.next; } index += 1 } if (found) { previous.next = current.next; if (previous.value === null) { this.head = current.next; } if (current.next === null) { this.tail = previous; } this.size -= 1; return index; } else { return -1; } } find(item) { let current = this.head; let count = 0; while (current !== null) { if (current.value === item) { return count; } else { current = current.next; count += 1; } } return -1; } iter() { let current = this.head; while (current !== null) { yield current.value; current = current.next; } } size() { return this.size; } clear() { this.head = null; this.tail = null; this.size = 0; } isEmpty() { return this.size === 0; }}复制代码