链表（python）
2021-04-02 19:28
标签：arch 结构 数据 代码 运用 set 连续 code 这一 一、链表和数组 在编写代码中，我们储存的数据是存储于内存当中，内存就像一块块并列排序的小方盒，每个小方盒都有自己地址，我们储存的数据就在这样一个个小方盒当中。 这些数据存放的结构有两种基本方式，数组和链表。 1，数组 数组在内存中是按顺序，内存地址来存储的，就好似上图的抽屉，从上到下，按顺序存放物品。这一特征也就意味着数据在内存中是相连的，紧紧不分开的，小的内存空间可能会装不下较多的数据，造成了内存空间浪费。 世界上许多事情有好有坏，有利有弊，数组也是如此，数据在内存中紧密相连，也就意味着牵一发而动全身，比如你想在数组中添加一项数据，这就好比一排已经排好队的士兵，每个人都有自己的编号，而此时你突然要插入其中。 你：“兄弟方便让个位置吗？” 你后面的士兵都一脸凶神恶煞地看着你，如果不是排长强力要求你插入其中，他们肯定不会让你入队，因为你的入队，让你身后的士兵的编号都要往后挪。 数组也是一样，当新加入一个数据时，这就意味着它后面的数据内存地址都要往后稍一稍，删除亦如此。 2，链表 和赋值原理 链表和在内存中排列整齐的数组不同，它们像一堆散兵游勇，散布于内存中，只要哪里有空隙就往哪里钻，链表高效地运用了内存空间。虽然它们看起来杂乱无章，但其实它们井然有序，暗号让它们紧紧相连。数据与数据之间有一条“暗号”的链子相连接，那个数据在首位，那个数据在第二位……在末尾都非常清楚。 这种“暗号”其实就是内存地址，如下图，长方形就是节点，一个节点包含了两个方面的内容，数据和“暗号”，这个“暗号”其实就是下一个节点的引用信息。 链表的第一个和最后一个节点最重要和最特殊，最后一个节点则意味着后面没有数据了，所以它指向None,第一个节点的内存地址需要一个地方来保存，所以设立一个head属性对第一个节点应用。 下面来实现节点代码,一个节点需要存放数据和对下一个数据的引用： 相信很多人都有疑问，为什么把下一个节点赋给上一个节点的next就实现了内存的引用呢？这与Python的特性有关，Python没有专门的指针，所有变量即是指针。 举一个例子，a = 6,一个简单的赋值，它在内存中是怎样实现的呢？ 首先在内存中会创建数据6，数据6在内存中有自己的内存地址，然后再把变量标签a指向6，如上图a这个长方形中，实际是数据6的内存地址。再比如，a,b = b,a, 这实际就是a指向原来b指向的地址，b指向原来a指向的地址。明白了内存中赋值的原理，那么对Python链表中，next = 下一个节点，就会很清晰了，next指向下一个节点的内存地址。 三，单链表的实现 1，链表的优点和缺点 链表插入和删除数据非常快，但读取数据非常慢 数组的读取非常快，因为它在内存中连续存储，插入和删除慢，是因为插入和删除都要改变相应的内存地址。 链表的插入和删除都很快，因为只要相应的改变节点中next的指向即可，链表访问一个特定数据时，必须沿着链表一个一个数据访问，所以读取很慢、 2，链表的方法 链表（python） 标签：arch 结构 数据 代码 运用 set 连续 code 这一 原文地址：https://www.cnblogs.com/qjjfzmx/p/13460664.html
class Node:
def __init__(self,x):
self.data = initdata #存放数据
self.next = None #对下一个节点的引用
def getData(self): #返回数据
return self.data
def getNext(self): #返回下一个节点
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
数组
链表
读取
O(1)
O(N)
插入
O(N)
O(1)
删除
O(N)
O(1)
from node import Node
class UnorderedList:
def __init__(self):
self.head = None
def add(self,item): #添加数据
temp = Node(item)
temp.setNext(self.head) #next指向表头，head为引用表头的信息
self.head = temp #在把head指向新增加的节点
def size(self): #返回链表的size
current =self.head
count = 0
while current != None:
count +=1
current = current.getNext()
return count
def search(self,item): #数据是否在链表中
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self): #删除某个数据
current = self.head
previous = None
found = False
while not found:
if current.getData == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())