linked list(链表) 建立
Node
链表的基本组成就是一个个Node，每个Node都需要包括两部分内容，一部分是自身的data，另一部分是下一个Node的reference。
class Node:
def __init__(self, init_data):
self.data = init_data
self.next = None
def get_data(self):
return self.data
def get_next(self):
return self.next
def set_data(self, new_data):
self.data = newdata
def set_next(self, new_next):
self.next = new_next 每一个链表都有一个Head和一个End结点，End结点的next为None。
无序链表
this list is unordered, the specific location of the new item with respect to the other items already in the list is not important. The new item can go anywhere.
add操作
python链表增加新结点的过程我觉得跟我用C语言写还是有差别的。
整个过程如图，增加的结点位于链表的头部，也就是说，向前增加新结点：
- 创建新结点
- 将新结点的next指向旧链表的head
- 将新链表的head设为新结点
‘遍历’操作(traverse)
get_next()方法是该操作中主要用到的函数。
size, search, remove 都是基于‘遍历’操作
size操作
- 找到head
- 沿着head一个个摸下去，摸一个count+1
search操作
- 找到head
- 沿着head一个个摸下去，摸到item返回True，摸不到继续往下摸
remove操作
想要remove掉一个node，必须找到此node的前后两个nodes，并把他们这两个nodes连接起来。
- 找到head
- 沿着head一个个摸下去，且实时记录前方的node，摸到对应的item后链接该node的前后两个nodes
- 如果remove的那个node正好是head，则直接把head权给予接下去的那个node
class UnorderList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head == None
def add(self, item):
temp = Node(item) #创建新结点
temp.set_next(self.head) #将新结点链接之前的list
self.head = temp #将新结点设为head
def size(self):
current = self.head
count = 0
while current != None:
count += count
current = current.get_next()
return count
def search(self, item):
current = self.head
found = False
while current != None and not found:
if current.get_data() == item:
found = True
else:
current = current.get_next()
return found
def remove(self, item):
current = self.head()
previous = None
found = False
while not found:
if current.get_data() == item:
found = True
else:
previous = current
current = current.get_next()
if previous == None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())如果你执行一个insert(0,item)操作在一个list上，时间复杂度为O(n)。 但是对于无序链表来说，执行一个相同的操作是需要O(1)的时间复杂度
有序链表
就是将无序链表中的每个node的data进行了变得有大小顺序了。Node的class没有变化。
class orderList:
def __init__(self): # 无变化
self.head = None
def is_empty(self): # 无变化
return self.head == None
def add(self, item): # 变化最大的在这里
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.get_data() > item:
stop = True
else:
previous = current
current = current.get_next()
temp = Node(item)
if previous == None:
temp.set_next(self.head)
self.head = temp
else:
temp.set_next(current)
previous.set_next(temp)
def size(self): # 无变化
current = self.head
count = 0
while current != None:
count += count
current = current.get_next()
return count
def search(self, item): # 其实基本没变化，stop可有可无
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.get_data() == item:
found = True
else:
if current.get_data() > item:
stop = True
else:
current = current.get_next()
return found
def remove(self, item): # 无变化
current = self.head()
previous = None
found = False
while not found:
if current.get_data() == item:
found = True
else:
previous = current
current = current.get_next()
if previous == None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())