1.无序列表的概念

一种数据按照其相对位置存放的数据集结构。其本身没有固定的顺序概念，为了便于查找引入了节点来联接不同的数据项。

2.无序列表的python实现

2.1 节点的建立

无序列表的概念比较抽象，但其思路是这样：创建节点→将节点连接形成链式结构。

将问题分成两部分就比较好理解了。第一部分是创建节点，创建节点的任务交给节点构造：第二部分是将节点联接形成链式结构，这部分任务交给无序表的构成。

首先是创建节点，节点需要具备两个特性一个是存储数据，一个是方向。下图是一个简单的链式结构图。

将指向节点的箭头称为首方向，从节点指出的箭头称为尾方向。

可以看到节点1只有尾方向，节点5只有首方向，节点2、3、4首尾方向都有。

我们叫节点1这种节点为首节点，节点5这种节点称为尾节点，其余节点称为中间节点。

重点看中间节点，中间节点有两个指向是否意味着我需要设置两个方向参数来表示节点的方向属性呢？

答案是不需要，两个方向存在一定的联系（该节点的首方向是上一个节点的尾方向），可以弱化降级为一个方向。

将方向降级处理后，又出现了新的问题，你需要选择哪个方向作为节点的方向属性。你可以选择首方向或者是尾方向，选择哪一个更好呢？下面我将两种选择对应的节点结构展现给你看。

选择首方向的节点结构：

选择尾方向的节点结构：

只展示节点的结构无法知晓哪种结构更好，我们将两种方式带入的链式结构的构造环境中尝试进行分析。

如图为采用首方向的链式联接方式

它的联接过程是这样的：

首先是生成一号节点，它的初始head头为None（空）；二号节点是跟在一号节点后面，三号节点同样如此。整个连接过程都需要从第一个节点一号节点开始复杂度是n！级。

如图为采用尾方向的链式联接方式

该节点结构的链式生成是从尾部开始的1→2→3计算级为O（n）级。

现在很明显了，选择尾方向的节点结构更好。

到现在我们确定了节点的结构：

现在来用python实现节点概念。

class Node:
    # 节点
    def __init__(self,data):
        # 方向属性和数据属性
        self.data = data
        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

2.2 链式结构的生成

目前已经完成了节点的设置，现在开始分析解决第二部分‘将节点联接形成链式结构’同时创建无序列表结构。

前面分析了节点的联接方式如图

链式结构的构成只需要在节点的基础上设置一个head头来确定即哪个是1号节点和一个添加节点的方法即可实现。

链式结构只多了一个基础属性head，python代码实现如下：

class UnorderedList:
    # 无序表的抽象定义
    def __init__(self):
        self.head = None

self.head为空就代表其为首节点。

接下来实现节点的添加，python代码如下：

def add(self,item):
  # 添加节点
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp

步骤如下：给定一个数据项→赋予给节点生成新节点→确定节点的尾部next→将链式结构的head头指向新节点。

2.3 赋予无序列表常规的操作功能

无序列表还有查找和移除功能。

查找功能相对简单只需要从头部开始遍历列表即可实现，python代码如下

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

移除功能相对麻烦一点，要移除数据需要移除存储数据的节点，然后将该节点的前后节点重新联接。根据这种移除机制可以发现移除有两种情况：

（1）移除发生在头部

当移除发生在头部时，该节点的前面没有节点，操作是直接将head头联接该节点的下一个节点

（2）移除发生在非头部

当移除发生在中部时，需要将要移除节点的前一个节点的next属性联接到需移除节点的下一个节点

移除功能的代码实现如下：

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:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

我们汇总整个过程得到完整的无序列表结构的代码：

#%%
class Node:
    # 节点
    def __init__(self,initdata):
        self.data = initdata
        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
class UnorderedList:
    # 无序表的抽象定义
    def __init__(self):
        self.head = None
    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count
    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
    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:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())