3.6列表

列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。更具体地说，这种列表称为无序列表。

3.6.1 无序列表的抽象数据类型

以下是无序列表的操作：

• List():创建一个空列表，他需要参数，返回一个空列表
• add(item):头插
• remove(item):移除元素item
• search(item):搜索元素item是否在链表里，返回一个boolean对象
• isEmpty():判断是否为空
• length():求元素的个数
• append(item):尾插
• index(item):返回item的下标
• insert(pos, item):在指定位置pos插入元素item
• pop():假设列表不为空并移除最后一个元素，并将该元素返回
• pop(pos):移除制定位置的元素并返回

3.6.2 实现无序列表：链表

为了实现无序列表我们要构建链表。无序列表需要维持元素之间的相对位置，但是并不需要在连续的内存空间中维护这些位置信息。需要注意的是，必须指明列表中第一个元素的位置，一旦知道第一个元素的位置就能根据链接信息推出后续元素的位置。指向链表第一个元素的引用被称作***头***。最后一个元素需要知道自己没有下一个元素。

      
"""
节点node是构建链表的基本数据结构。每一个节点对象都必须至少持有两份信息：
   -1.节点必须包含列表元素，我们称之为节点的数据变量。
   -2.节点必须保存指向下一个节点的引用。
"""

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 isEmpty(self):
       return self.head == None

   def add(self, item):
       temp = Node(item) #创建一个新节点，列表中的每一个元素都必须放在一个节点对象中
       #将新节点与已有链表连接起来这一过程需要两部：
       #step1：将新节点的next引用指向当前链表的第一个节点
       temp.setNext(self.head)
       #step2：修改链表的头节点使其指向新建的节点
       self.head = temp
       #上述两部顺序非常重要，如果颠倒顺序所有节点都将丢失无法访问

   def length(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())

   def append(self, item):
       last = Node(item)
       found = False
       current = self.head
       while not found:
           if current.getNext() == None:
               found = True
           else:
               current = current.getNext()

       current.setNext(last)

   def insert(self, position, item):
       node = Node(item)
       found = False
       current = self.head
       previous = None
       count = 0

       while not found:
           if count == position:
               found = True
           else:
               previous = current
               current = current.getNext()
               count += 1

       if previous == None:
           node.setNext(self.head)
           self.head = node
       else:
           node.setNext(current)
           previous.setNext(node)

   def index(self, item):
       current = self.head
       found = False
       count = 0
       while current != None and not found:
           if current.getData() == item:
               found = True
           else:
               current = current.getNext()
               count += 1

       if found:
           return count
       else:
           return -1

   def pop(self, position=''):
       if position == '':
           found = False
           current = self.head
           previous = None
           while not found:
               if current.getNext() == None:
                   found = True
               else:
                   previous = current
                   current = current.getNext()

           if previous == None:
               self.head = current.getNext()
               return current.getData()
           else:
               previous.setNext(current.getNext())
               return current.getData()

       elif position == 0:
           current = self.head
           self.head = current.getNext()
           return current.getData()

       else:
           found = False
           current = self.head
           previous = None
           count = 0
           while not found:
               if count == position:
                   found = True
               elif current == None:
                   break
               else:
                   previous = current
                   current = current.getNext()
                   count += 1

           if previous == None:
               self.head = current.getNext()
               return previous.getData()
           elif current == None:
               return None
           else:
               previous.setNext(current.getNext())
               return current.getData()


#以列表的形式显示无序链表
   def showByList(self):
       current = self.head
       stop = False
       res = []
       while not stop:
           if current.getNext() == None:
               res.append(current.getData())
               stop = True
           else:
               res.append(current.getData())
               current = current.getNext()

       return res