单链表的学习(数据结构)

  1  """
  2 单链表学习程序
  3 重点程序
  4 """
  5 
  6 
  7 # 创建结点类
  8 class Node(object):
  9     def __init__(self, val, next=None):
 10         self.val = val  # 有用数据
 11         self.next = next
 12 
 13 
 14 # 链表的操作
 15 class LinkList(object):
 16     def __init__(self):
 17         self.head = Node(None)  # 链表的开头
 18 
 19     def init_list(self, data):
 20         p = self.head  # 可移动变量ｐ
 21 
 22         for i in data:
 23             p.next = Node(i)
 24             p = p.next
 25 
 26     def show(self):
 27         p = self.head.next
 28 
 29         while p != None:
 30             print(p.val, end=‘ ‘)
 31             p = p.next
 32         print()
 33 
 34     # 　尾部插入新的结点
 35     def append(self, item):
 36         p = self.head
 37         while p.next is not None:
 38             p = p.next
 39         p.next = Node(item)
 40 
 41     #  获取链表长度
 42     def get_length(self):
 43         n = 0
 44         p = self.head
 45         while p.next is not None:
 46             n += 1
 47             p = p.next
 48         return n
 49 
 50     # 　判断链表是否为空
 51     def is_empty(self):
 52         if self.get_length() == 0:
 53             return True
 54         else:
 55             return False
 56 
 57     # 清空链表
 58     def clear(self):
 59         self.head.next = None
 60 
 61     # 　获取索引值
 62     def get_item(self, index):
 63         p = self.head.next
 64         i = 0
 65         #　没有到对应索引号并且遍历索引没有到最后就循环
 66         while i < index and p is not None:
 67             i += 1
 68             p = p.next
 69         # 如果因为ｐ到最后了则说明越界
 70         if p is None:
 71             raise IndexError("list index out of range")
 72         # ｉ 不小于　ｉｎｄｅｘ说明找到索引结点了
 73         else:
 74             return p.val
 75 
 76     def insert(self,index,item):
 77         if index < 0 or index > self.get_length():
 78             raise IndexError("list index out of range")
 79 
 80         #　让ｐ移动到待插入位置的前一个
 81         p = self.head
 82         i = 0
 83         while i < index:
 84             p = p.next
 85             i += 1
 86 
 87         node = Node(item)  #　创建新的结点
 88         node.next = p.next  #　插入结点
 89         p.next = node
 90     #p.next=Node(item,p.next) # 一句话完成
 91 
 92     def delete(self,item):
 93         p = self.head
 94         while p.next is not None:
 95             #　如果值相等则越过中间的结点
 96             if p.next.val == item:
 97                 p.next = p.next.next
 98                 break
 99             p = p.next # 让程序继续前进
100         else:
101             raise ValueError("x not in list")
102 
103 
104 if __name__ == "__main__":
105     # 　创建链表对象
106     link = LinkList()
107 
108     # 　初始数据
109     l = [1, 2, 3, 4, 5]
110     link.init_list(l)  # 将初始数据插入链表
111     link.show()  # 遍历链表
112     link.append(6)  # 尾部插入结点
113     link.show()
114     print(link.get_length())  # 获取结点个数
115 
116     # print(link.is_empty())  # 判断是否为空
117     # link.clear()  # 清空链表
118     # print(link.is_empty())
119 
120     print(link.get_item(4)) #　获取索引值
121 
122     link.insert(1,10) # 在某个索引位置插入数据
123     link.show()
124     link.delete(10000)
125     link.show()