python获取链表长度

Python数据结构之单链表

单链表有后继结点，无前继结点。

以下实现：

创建单链表

打印单链表

获取单链表的长度

判断单链表是否为空

在单链表后插入数据

获取单链表指定位置的数据

获取单链表指定元素的索引

删除单链表指定位置的元素

更新单链表指定位置的元素

清空单链表

class Node(object):

"""定义类来描述指针"""

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

self.data = data

self.next = p

class LinkList(object):

"""单链表"""

def __init__(self):

self.head = None

# 初始化单链表

def create(self, data):

self.head = Node(data[0])

p = self.head

for i in data[1:]:

p.next = Node(i)

p = p.next

# 打印单链表

def print(self):

p = self.head

while p != None:

print(p.data)

p = p.next

# 获取单链表的长度

def len(self):

p = self.head

length = 0

while p != None:

length += 1

p = p.next

return length

# 判断单链表是否为空

def is_empty(self):

return self.len() == 0

# 在单链表后插入数据

def append(self, item):

if self.is_empty():

self.head = Node(item)

else:

p = self.head

while p.next != None:

p = p.next

p.next = Node(item)

# 获取单链表指定位置的数据

def getItem(self, index):

if self.is_empty():

print("单链表为空")

return

if index >= self.len() or index < 0:

print("索引超过单链表长度")

return

p = self.head

count = 0

while count != index:

p = p.next

count += 1

return p.data

# 获取单链表指定元素的索引

def find(self, item):

p = self.head

index = 0

while p != None:

if p.data == item:

return index

p = p.next

index += 1

print("单链表中不存在" + repr(item))

# 在单链表指定位置插入元素

def insert(self, index, item):

if self.is_empty():

print("单链表为空")

return

if index >= self.len() or index < 0:

print("索引超过单链表长度")

return

if index == 0:

self.head = Node(item, self.head)

else:

p = self.head

count = 0

while count < index-1:

p = p.next

count += 1

p.next = Node(item, p.next)

# 删除单链表指定位置的元素

def delete(self, index):

if self.is_empty():

print("单链表为空")

return

if index >= self.len() or index < 0:

print("索引超过单链表长度")

return

if index == 0:

self.head = self.head.next

else:

p = self.head

count = 0

while count < index-1:

p = p.next

count += 1

p.next = p.next.next

# 更新单链表指定位置的元素

def update(self, index, data):

if self.is_empty():

print("单链表为空")

return

if index > self.len() or index < 0:

print("索引超过单链表长度")

return

p = self.head

count = -1

while count < index-1:

p = p.next

count += 1

p.data = data

# 清空单链表

def clear(self):

self.head = None

L = LinkList()

L.create([1, 2, 3])

print("打印单链表：")

L.print()

print("获取单链表的长度：")

print(L.len())

print("单链表是否为空")

print(L.is_empty())

print("在单链表后插入数据")

L.append(4)

L.print()

index = 1

print("获取第" + repr(index) + "个位置的数据")

print(L.getItem(index))

item = 3

print("获取单链表中元素" + repr(item) + "的索引")

print(L.find(item))

index = 2

item = 10

print("在单链表的" + repr(index) + "位置插入数据" + repr(item))

L.insert(index, item)

L.print()

index = 2

print("删除单链表"+repr(index)+"位置的元素")

L.delete(index)

L.print()

index = 2

item = 100

print("更新单链表"+repr(index)+"位置的元素为"+repr(item))

L.update(index, item)

L.print()

print("清空单链表")

L.clear()

L.print()

程序输出结果：

打印单链表：

1

2

3

获取单链表的长度：

3

单链表是否为空

False

在单链表后插入数据

1

2

3

4

获取第1个位置的数据

2

获取单链表中元素3的索引

2

在单链表的2位置插入数据10

1

2

10

3

4

删除单链表2位置的元素

1

2

3

4

更新单链表2位置的元素为100

1

2

100

4

清空单链表