mingrixing 2019-06-28
线性数据结构有两端,有时被称为左右,某些情况被称为前后。你也可以称为顶部和底部,名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式,特别是添加和移除项的位置。例如一些结构允许从一端添加项,另一些允许从另一端移除项。
数组(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 | 清空链表 |
# python3 class Node: def __init__(self, value=None, next=None): self.value = value self.next = next class 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
// ES6 class 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; } }