0°

Python数据结构实现之链表

内容预览:
  • 注2:这些节点在逻辑上是相连的,但要知道它们在物理内存上并不相连~
  • 2、准备工作 2.1 Node类 我们先来实现Node类: class Node(object): &nb...~
  • def add(self, item):    # Step0:创建一个新节点并将新项作...~

始发于微信公众号: Python那些事

(点击上方公众号,可快速关注一起学Python)

1、简单介绍

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。—— 维基百科

链表的基本构造块是节点(Node)。我们将在文章的第2部分通过Python实现一个简单的Node类。

一个单向链表的构造如下图所示包含两个域:

    信息域:当前节点的值(Data or Value)

    指针域:指向下一个节点的指针链接(Reference or Link)

Python数据结构实现之链表

注1:必须明确指定链表的第一项的位置。一旦我们知道第一项在哪里,第一项目可以告诉我们第二项是什么,依次类推。按照一个方向遍历,直到最后一项(最后一个节点),最后一项需要知道没有下一项。
注2:这些节点在逻辑上是相连的,但要知道它们在物理内存上并不相连。

2、准备工作

2.1 Node类

我们先来实现Node类:

class Node(object):
   def __init__(self, initdata):
       self.data = initdata
       # 引用None代表没有下一节点
       self.next = None
   # 获得数据
   def getData(self):
       return self.data
   # 获得下一个节点的引用
   def getNext(self):
       return self.next
   # 修改数据
   def setData(self, newdata):
       self.data = newdata
   # 修改下一节点的引用
   def setNext(self, newnext):
       self.next = newnext

创建一个Node对象试试:

>>> tmp = Node(33)
>>> tmp
<__main__.Node object at 0x1022699b0>
>>> tmp.getData()
33

2.2 Unordered List类

只要知道第一个节点(包含第一个项),那么之后的每个节点都可以通过指向下一个节点的链接 依次找到。
考虑到这样的情况,Unordered List类只要维护对第一个节点的引用就可以了。Unordered List类本身不包含任何节点对象,它只包含对链表结构中第一个节点的单个引用!

class unOrderedList():
   def __init__(self):
       # 初始化None表示此时链表的头部不引用任何内容
       self.head = None

创建一个空的链表试试:

>>> myList = unOrderedList()

Python数据结构实现之链表

我们可通过下面的 isEmpty() 方法检查是否为空链表:

# 只有在链表中没有节点的时候为真
def isEmpty(self):
   return self.head == None

添加元素后的链表是这样的,稍后在文章第3部分实现添加方法:

Python数据结构实现之链表

3、基本操作的实现


3.1 add()在链表前端添加元素

由于是在前端添加,因此最后添加的在最前端。

def add(self, item):
   # Step0:创建一个新节点并将新项作为数据
   temp = Node(item)
   # Step1:更改新节点的下一个引用以引用旧链表的第一个节点
   temp.setNext(self.head)
   # Step2:重新设置链表的头以引用新节点
   self.head = temp

添加元素——执行mylist.add(26)时候的图解如下:

>>> mylist.add(31)
>>> mylist.add(77)
>>> mylist.add(17)
>>> mylist.add(93)
>>> mylist.add(26)

Python数据结构实现之链表

3.2 size()求链表长度

def size(self):
   current = self.head
   count = 0
   while current != None:
       count += 1
       current = current.getNext()
   return count

通过current遍历链表并对节点计数。
图解如下:

Python数据结构实现之链表

3.3 search()查找

def search(self, item):
   current = self.head
   found = False
   while current != None and not found:
       if current.getData() == item:
           found = True
       else:
           current = current.getNext()
   return found

通过current遍历链表,使用found标记是否找到了正在寻找的项。
图解如下:

Python数据结构实现之链表

3.4 remove()删除

def remove(self, item):
   current = self.head
   previous = None
   found = False
   while not found:
       if current.getData() == item:
           found = True
       else:
           previous = current
           current = current.getNext()
   if previous == None:
   # 当要删除的项目恰好是链表中的第一个项,这时候prev是None,需要修改head以引用current之后的节点
       self.head = current.getNext()
   else:
       previous.setNext(current.getNext())

3.4.1 上面的特殊情况,即要删除的恰好是第一个节点的图解如下:

Python数据结构实现之链表

3.4.2 其他情况,即要删除的是链表中的节点(非第一个):

我们遍历链表,先搜索,再删除。

    1.搜索:


  • 使用previous与current进行移动,借助found标记是否找到。

  • 一旦found为True,current就是对包含要删除的项的节点的引用。


    2.删除(修改引用):


  • 我们把previous的对下一节点的引用设为current的下一节点。


以上两过程的图解如下:

参考:

http://interactivepython.org/runestone/static/pythonds/index.html

https://en.wikipedia.org/wiki/Python


看完本文有收获?请转发分享给更多人

关注「Python那些事」,提升Python技能

以上就是:Python数据结构实现之链表 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论