数据结构----链表Link

链表简介与数据结构

　　单向链表也叫单链表，是表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。　　

单向链表的抽象数据类型定义：

　　　　　　. is_empty()：链表是否为空

　　　　　　. length()：链表长度

　　　　　　. travel()：遍历整个链表

　　　　　　. add(item)：链表头部添加元素

　　　　　　. append(item)：链表尾部添加元素

　　　　　　. insert(pos, item)：指定位置添加元素

　　　　　　. remove(item)：删除节点

　　　　　　. search(item)：查找节点是否存在

链表的定义　　

 1 class Node(object):
 2     def __init__(self, item):
 3         self.item = item
 4         self.next = None
 5 
 6 
 7 class Link(object):
 8     def __init__(self):
 9         self._head = None
10 
11     def isEmpty(self):
12         return self._head is None
13 
14     @property
15     def length(self):
16         node = self._head
17         count = 0
18         while node:
19             count += 1
20             node = node.next
21         return count
22 
23     def travel(self):
24         if self._head:
25             cur_node = self._head
26             while cur_node:
27                 print(cur_node.item)
28                 cur_node = cur_node.next
29         else:
30             raise ("<The object is empty!>")
31 
32     def add(self, item):
33         node = Node(item)
34         node.next = self._head
35         self._head = node
36 
37     def append(self, item):
38         node = Node(item)
39         if self.isEmpty():
40             self._head = node
41         else:
42             cur_node = self._head
43             while cur_node:
44                 pre_node, cur_node = cur_node, cur_node.next
45             pre_node.next = node
46 
47     def insert(self, item, index):
48         if index <= 0:  # 插入位置索引小于等于0都是在头部插入
49             self.add(item)
50         elif index >= self.length:  # 插入位置索引大于等于链表长度时都是在尾部插入
51             self.append(item)
52         else:  # 插入位置索引index在1到链表length-1之间
53             node = Node(item)
54             cur_node = self._head.next
55             pre = self._head
56             count = 1
57             while cur_node:
58                 if count == index:
59                     pre.next, node.next = node, cur_node
60                     break
61                 pre, cur_node = cur_node, cur_node.next
62                 count += 1
63 
64     def remove(self, item):
65         if self.isEmpty():  # 空提示
66             return "Failed because of Empty!"
67         cur_node = self._head
68         pre_node = None
69         while cur_node:
70             if cur_node.item == item:
71                 if pre_node == None:  # 删除的索引为0
72                     self._head = cur_node.next
73                 else:
74                     pre_node.next = cur_node.next
75                 return item
76             pre_node, cur_node = cur_node, cur_node.next
77         raise ("Not found!")  # 最后没有找到报错
78 
79     def search(self, item):
80         if self.isEmpty():
81             raise ("<The object is empty!>")
82         else:
83             cur_node = self._head
84             index = 0
85             while cur_node:
86                 if cur_node.item == item:
87                     return index
88                 index += 1
89                 cur_node = cur_node.next
90             return -1

链表的使用　　

1 link = Link()
2 link.append(2)
3 link.append(3)
4 link.add(4)
5 link.insert(11, 1)
6 link.remove(4)
7 link.travel()
8 print(link.length)
9 print(link.search(11))