# Python實現的資料結構與演算法之連結串列詳解

① SinCycLinkedlist() 建立單向迴圈連結串列
② add(item) 向連結串列中插入資料項
③ remove(item) 刪除連結串列中的資料項
④ search(item) 在連結串列中查詢資料項是否存在
⑤ empty() 判斷連結串列是否為空
⑥ size() 返回連結串列中資料項的個數

Python的內建型別list底層是由C陣列實現的，list在功能上更接近C 的vector（因為可以動態調整陣列大小）。我們都知道，陣列是連續列表，連結串列是連結列表，二者在概念和結構上完全不同，因此list不能用於實現連結串列。

``````
#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
def __init__(self, initdata):
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
class SinCycLinkedlist:
def __init__(self):
self.head = Node(None)
self.head.setNext(self.head)
def add(self, item):
temp = Node(item)
temp.setNext(self.head.getNext())
self.head.setNext(temp)
def remove(self, item):
prev = self.head
while prev.getNext() != self.head:
cur = prev.getNext()
if cur.getData() == item:
prev.setNext(cur.getNext())
prev = prev.getNext()
def search(self, item):
cur = self.head.getNext()
while cur != self.head:
if cur.getData() == item:
return True
cur = cur.getNext()
return False
def empty(self):
return self.head.getNext() == self.head
def size(self):
count = 0
cur = self.head.getNext()
while cur != self.head:
count  = 1
cur = cur.getNext()
return count
if __name__ == '__main__':
s = SinCycLinkedlist()
print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
s.add(19)
s.add(86)
print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
print('86 is%s in s' % ('' if s.search(86) else ' not',))
print('4 is%s in s' % ('' if s.search(4) else ' not',))
print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))
s.remove(19)
print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))``````

``````
\$ python sincyclinkedlist.py
s.empty() == True, s.size() == 0
s.empty() == False, s.size() == 2
86 is in s
4 is not in s
s.empty() == False, s.size() == 2
s.empty() == False, s.size() == 1``````