数据结构--单链表-白红宇

数据结构--单链表

阅读量：5312 次

发布时间：2019-06-14

本文共 3406 字，大约阅读时间需要 11 分钟。

#!/use/bin/env python

#encoding=gbk

import sys

class Node():

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

self.data = data

self.next = next

"""

单链表:

1. 初始化单链表

2. 单链表是否为空

3. 单链表的长度

4. 获得单链表指定位置的元素

5. 重置指定位置的单链表的元素

6. 在单链表指定位置插入一个元素

7. 在单链表的尾部追加一个元素

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

9. 清空单链表

10. 打印单链表的内容

"""

class LinkedList():

def __init__(self):

self.head = None

def initList(self, data):

self.head = Node(data[0])

pointer = self.head

for i in range(1,len(data)):

node = Node(data[i])

pointer.next = node

pointer = pointer.next

def isEmpty(self):

if self.head == None:

return True

return False

def length(self):

pointer = self.head

length = 0

while pointer != None:

length += 1

pointer = pointer.next

return length

def get(self, index):

if self.head != None and index > -1:

pointer = self.head

j = 0

while pointer != None and j < index:

j += 1

pointer = pointer.next

if pointer != None:

return pointer

return None

def set(self, index, element):

if self.head != None and index > -1:

pointer = self.head

j = 0

while pointer != None:

if j == index:

pointer.data = element

j += 1

pointer = pointer.next

return 0

return -1

def setx(self, index, element):

node = self.get(index)

if node != None:

node.data = element

return -1

def add(self, index, element):

if self.head != None:

if index <= 0:

print "index:[%d],insert head!"%index

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

return True

else:

pointer = self.head

j = 0

while pointer.next != None and j < index - 1:

j += 1

pointer = pointer.next

pointer.next = Node(element, pointer.next)

return True

return False

else:

print "the linked list is empty!"

return False

def append(self, element):

return self.add(sys.maxint, element)

def remove(self, index):

if self.head != Node:

if index == 0:

print "index:[%d],remove head!"%index

self.head = self.head.next

return True

else:

pointer = self.head

j = 0

while pointer.next != Node and j < index - 1:

j += 1

pointer = pointer.next

if pointer.next != None:

pointer.next = pointer.next.next

return True

else:

print "the linked list is empty!"

return False

def clear(self):

self.head = None

return 0

def show(self):

if self.head != None:

showInfo = ""

pointer = self.head

while pointer != None:

showInfo += "%s "%(pointer.data)

pointer = pointer.next

return showInfo.strip()

return None

if __name__ == '__main__':

linkedList = LinkedList()

print "linked list is empty:[%s]"%linkedList.isEmpty()

linkedList.initList(["tom","jim","jack","json"])

print "linked list is empty:[%s]"%linkedList.isEmpty()

print "linked list's length:[%d]"%linkedList.length()

node = linkedList.get(3)

print "linked list's third element is:[%s]"%(node.data)