算法——数据结构（单向链表的实现）

青旅半醒 2022-05-09 07:26 172阅读 0赞

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

*  表元素域elem用来存放具体的数据。
 *  链接域next用来存放下一个节点的位置（python中的标识）
 *  变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

**节点实现**

class SingleNode(object): def __init__(self,item): self.item = item # 存放数据元素 self.next = None

**功能实现**

class SingleLinkList(object): def __init__(self): self._head = None def is_empty(self): """判断链表是否为空""" return self._head == None def length(self): """链表长度""" cur = self._head count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): """遍历链表""" cur = self._head while cur != None: print cur.item, cur = cur.next print "" def add(self, item): """头部添加元素""" node = SingleNode(item) if self.is_empty(): self._head = node else: cur = self._head while cur.next != None: cur = cur.next cur.next = node def insert(self, pos, item): if pos <= 0: self.add(item) elif pos > (self.length() - 1): self.append(item) else: node = SingNode(item) count = 0 pre = self._head while count < (pos-1): count += 1 pre = pre.next node.next = pre.next def remove(self, item): """删除节点""" cur = self._head pre = None while cur != Node: if cur.item == item: if not pre: self._head = cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next def search(self, item): cur = self._head while cur != None: if cur.item == item: return True cur = cur.next return False

**操作测试**

if __name__ == "__main__": ll = SingleLinkList() ll.add(1) ll.add(2) ll.append(3) ll.insert(2, 4) print "length:",ll.length() ll.travel() print ll.search(3) print ll.search(5) ll.remove(1) print "length:",ll.length() ll.travel()