一，线性结构

1.Array

Array文档：可以自行阅读相关文档来了解Array

class array.array(typecode[, initializer])

 

 

array.append(x)：添加元素到数组末尾

array.count(x)：计算元素出现次数

array.extend(iterable)：将迭代器中的元素依次添加到数组末尾，不过要注意元素的类型要一致，要不然会抛出TypeError

array.fromfile(f, n)：读取文件中n个元素，如果文件中元素数量小于n，抛出EOFError，不过之前写入的数据仍然存在。

array.fromlist(list)：与上例差不多，相当于for x in list: a.append(x)，类型要一致。

array.fromstring(s)：与上例差不多。

array.index(x)：返回第一次元素出现的下标。

array.insert(i, x)：将元素x插入到i的位置上。

array.pop([i])：移除i下标的元素并且返回这个值，默认-1（最后一个）。

array.remove(x)：移除掉第一个x元素，不对后续x元素处理。

array.reverse()：反转数组。

array.tofile(f)：把数组内容写到文件中。

array.tolist()：把数组转化为列表，不改变内容。

array.tostring()：把数组转化为字符串。

array.tounicode()：和tostring差不多，但是要注意数组类型是'u'。要不然会抛出ValueError。

文档内容差不多就这些，大部分是写方法，加粗的为不常用的，还有一些方法会有些版本限制，稍微注意。

2.List实现Array部分功能

 

3.代码实现

class Array():def __init__(self,size):self.__size = sizeself.__item = [None]*sizeself.__length = 0def __setitem__(self,key,value):self.__item[key] = valueself.__length += 1def __getitem__(self, index):return self.__item[index]def __len__(self):return self.__lengthdef __iter__(self):for value in self.__item:yield valuedef remove(self,value):for i,ele in enumerate(self.__item):if ele == value:self.__item[i] = Nonereturnif __name__ == '__main__':a1 = Array(10)a1[0] = 1a1[1] = 2a1[2] = 3a1[3] = 4a1.remove(2)for value in a1:print(value)

 

 

二，链式结构

1.单链表

1.基本原理

和线性结构不同，链式结构内存不连续的，而是一个个串起来的，这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。 这里可不要混淆了列表和链表（它们的中文发音类似，但是列表 list 底层其实还是线性结构，链表才是真的通过指针关联的链式结构）。 看到指针你也不用怕，这里我们用的 python，你只需要一个简单赋值操作就能实现，不用担心 c 语言里复杂的指针。

先来定义一个链接表的节点，刚才说到有一个指针保存下一个节点的位置，我们叫它 next， 当然还需要一个 value 属性保存值。

class Node:def __init__(self, value, next=None):self.value = valueself.next = next

然后就是我们的单链表 LinkedList ADT:

class LinkedList(object):""" 链接表 ADT[root] -> [node0] -> [node1] -> [node2]"""

 

 

2.代码实现

class Node():def __init__(self,value=None,next=None):self.value = valueself.next = nextdef __str__(self):return 'Node:{}'.format(self.value)class LinkedList():def __init__(self):self.root = Node()self.size = 0self.next = None#增加新数据时，将新数据地址与谁关联def append(self,value):node = Node(value)if not self.next:self.root.next = nodeelse:self.next.next = nodeself.next = nodeself.size += 1def append_first(self,value):node = Node(value)if not self.next:self.root.next = nodeself.next = nodeelse:temp = self.root.nextself.root.next = nodenode.next = tempself.size += 1def __iter__(self):current = self.root.nextif current:while current is not self.next:yield currentcurrent = current.nextyield currentdef find(self,value):for n in self.__iter__():if n.value == value:return ndef find_count(self,value):count = 0for n in self.__iter__():if n.value == value:count += 1return countdef remove(self,value):prev = self.rootfor n in self.__iter__():if n.value == value:if n == self.next:prev.next == Noneself.next = prevprev.next = n.nextdel nself.size -= 1return Trueprev = ndef remove_all(self,value):prev = self.rootfor n in self.__iter__():if n.value == value:if n == self.next:prev.next == Noneself.next = prevprev.next = n.nextdel nself.size -= 1continueprev = nif __name__ == '__main__':link = LinkedList()link.append(11)link.append(11)link.append(11)link.append(14)link.append(15)link.append(16)for value in link:print(value)print(link.find(11))print(link.find_count(11))link.remove(16)for value in link:print(value)link.remove_all(11)print("--"*20)for value in link:print(value)

 

2.双链表

上边我们亲自实现了一个单链表，但是能看到很明显的问题，单链表虽然 append 是 O(1)，但是它的 find 和 remove 都是 O(n)的， 因为删除你也需要先查找，而单链表查找只有一个方式就是从头找到尾，中间找到才退出。 我们需要在一个链表里能高效的删除元素， 并把它追加到访问表的最后一个位置，这个时候单链表就满足不了了。

1.基本原理

这里就要使用到双链表了，相比单链表来说，每个节点既保存了指向下一个节点的指针，同时还保存了上一个节点的指针。

class Node(object):def __init__(self, value=None, prev=None, next=None):self.value, self.prev, self.next = value, prev, next

• 看似我们反过来遍历双链表了。反过来从哪里开始呢？我们只要让 root 的 prev 指向 tail 节点，不就串起来了吗？
• 直接删除节点，当然如果给的是一个值，我们还是需要查找这个值在哪个节点？ - 但是如果给了一个节点，我们把它拿掉，直接让它的前后节点互相指过去不就行了？哇欧，删除就是 O(1) 了，两步操作就行啦

 

 

 

2.代码实现

class Node():def __init__(self,value=None,prev=None,next=None):self.value = valueself.next = nextself.prev = prevdef __str__(self):return "Node:{}".format(self.value)class DoubleLinkedList():def __init__(self):self.size = 0self.root = Node()self.end = Nonedef append(self,value):node = Node(value=value)#无节点if not self.end:self.root.next = node  # root节点指向新节点node.prev = self.root#新节点指向根节点self.end = node#末节点指针指向新节点#有节点else:self.end.next = node#末节点指向新节点node.prev = self.end  # 新节点指向末节点self.end = node#末节点移动到新节点self.size += 1def append_first(self,value):node = Node(value=value)#无节点if not self.end:self.root.next = node  # root节点指向新节点node.prev = self.root  # 新节点指向根节点self.end = node  # 末节点指针指向新节点else:node.prev = self.root#新节点指向根节点temp = self.root.next#保存原来的第一个节点self.root.next = node#将新节点替换为第一个节点node.next = temp#让新节点的下一个节点为原来的第一个节点temp.prev = node#将原来的第一个节点的上一个节点设置为新节点self.size += 1def __iter__(self):current = self.root.nextif current:while current is not self.end:yield currentcurrent = current.nextreturn currentelse:print("LinkedList is empty")#逆向迭代def inverse_iter(self):current = self.endif current:while current is not self.root:yield currentcurrent = current.prevelse:print("LinkedList is empty")def find(self,value):passdef find_count(self,value):passdef remove(self,value):passdef remove_all(self,value):passif __name__ == '__main__':link = DoubleLinkedList()link.append(11)link.append(12)link.append(13)link.append(14)link.append(15)gen = (link.inverse_iter())for value in gen:print(value)