python实现单链表_python 实现单链表

参考《数据结构与算法：python语言描述》（裘宗燕）

链表（也叫线性表）定义：链表是一种动态的数据结构，可以由一组任意的存储结构组成，每个元素作为一个结点，每个结点由数据域和指针域构成。

实现一个链表需要的条件：

能直接或间接的找到表中首元素

从表中任一元素出发，能找到它之后的下一元素

线性表有两种存储方式： a.顺序表（将元素保存在连续的存储区） b.链表

链表的实现方式如下：

1.把表中的元素分别存储在一批独立的存储块（称为表结点）里

2.保重从组成表结构中的任一个结点可以找到与其相关的下一个结点

3.在前一结点里用链接的方式显示的记录与下一结点之间的联系

说明：拿python来说，我们可以使用类来构成一个结点，然后增加两个属性，一个数据属性，一个指针属性，这样就可以构成一个简单的结点。

抽象一个链表：

ADT List:

List(self)

is_empty(self)

len(self)

prepend(self,elem)

append(self,elem)

insert(self,elem,i)

del_first(self)

del_last(self)

del(self,i)

search(self,elem)

forall(self,op)

定义一个结点

class LNode:

def __init__(self, data, next_=None):

self.data = data

self.next_ = next_

单链表

class LinkedList:

def __init__(self):

# 头指针

self.head = None

# 尾指针

self.tail = None

def append(self, data):

# 实例化一个结点

node = LNode(data)

# 如果是空链表

if not self.head:

self.head = node

self.tail = node

else:

self.tail.next_ = node

self.tail = node

def insert(self, index, value):

cur = self.head

cur_index = 0

if not cur:

raise Exception('This is en empty linked list')

# 查找插入位置的上一个结点（这步没有考虑好最后一个结点指向None的问题）

while cur_index < (index - 1):

cur = cur.next_

if not cur:

raise Exception('list length less than index ')

cur_index += 1

node = LNode(value)

node.next_ = cur.next_

cur.next_ = node

# 如果结点链接域指向None

if not node.next_:

self.tail = node

def remove(self, index):

cur = self.head

cur_index = 0

if not cur:

raise Exception('This is en empty linked list')

while cur_index < (index - 1):

cur = cur.next_

if not cur:

raise Exception('List length less than index')

cur_index += 1

if index == 0:

self.head = cur.next_

return

if self.head is self.tail:

self.head = None

self.tail = None

return

cur.next_ = cur.next_.next_

if not cur.next_:

self.tail = cur.next_

def iter(self):

if not self.head:

return None

cur = self.head

yield cur.data

while cur.next_:

cur = cur.next_

yield cur.data

def is_empty(self):

return not self.head

if __name__ == 'main':

ll = LinkedList()

for i in range(5):

ll.append(i)

ll.insert(2, 'r')

print(list(ll.iter()))

ll.remove(5)

print(list(ll.iter()))

print(ll.sort())