数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。最近浏览了27-31，主要内容是使用链表数据结构实现有序列表、无序列表。

无序列表实现

列表本身按照相对位置存放数据，List就是无序表
add(),append(),insert(0,item),index(item)返回数据项在表中的位置,pop(pos)移除指定位置数据项
采用链表实现无序表，因为数据项前后位置的保存不要求数据项依次存放在连续的存储空间
链接指向 和 前后相对位置
数据节点Node是链表实现的基本结构，包含数据和下一节点的位置信息

class Node:
    def __init__(self, initdata):
        self.data= initdata
        self.next=None#next 保存下一个节点

    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

访问节点必须从第一个开始遍历，所以无序表必须要有对第一个节点的引用信息
设立一个属性head，保存对第一个节点的引用。空表的head是None。
无序表本身并不包含数据项。数据项保存在节点中。
添加新的数据项最快的地方是链表的首位

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):
        count=0
        current=self.head
        while current!=0:
            count=count+1
            current=current.getNext()
        return count

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

    #remove实现，需要保留前一个节点的next
    def remove(self,item):
        current=self.head
        previous=None
        if item==current.getData():
            self.head=current.getNext()
        else:
            while current!=None:
                previous=current
                current=current.getNext()
                if current.getData()==item:
                    previous.setNext(current.getNext())
                else:
                    previous=previous.getNext()
                    current=current.getNext()     
        return item

    def pop(pos):
        current=self.head
        out=None
        i=0
        if pos==0:
            out=current.getData()
            self.head=current.getNext()
        if pos>0:
            while i<pos:
                i+=1
                previous=current
                current=current.getNext()
        previous.setNext(current.getNext())
        out=current.getData()
        return out

    #双链表，每个节点两个指针，分别表示上下

有序列表实现

有序列表抽象数据类型及实现——OrderedList
数据依照其某种科比性质来决定在列表中的位置

"""
add(item)保持整体顺序
remove(item)
search(item)
index(item)
size()
pop()
pop(pos)
"""

数据项的相对位置取决于大小比较，Python中只要定义了gt方法的都适用
同样采用链表实现，公用Node

class OrderedList:
    def __init__(self):
        self.head=None
    #isEmpty(),size(),remove()跟节点次序无关

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

    #Search/add则需要修改，search可以提前结束
    def search(self,item):
        current=self.head
        found=False
        stop=False
        while current!=None and not found and not stop:
            if current.getData() ==item:
                found=True
            else:
                if current.getData()>item:
                    stop=True
                else:
                    current=current.getNext()
    
    def add(self,item):
        current=self.head
        previous=None
        stop=False
        while current!=None and not stop:
            if current.getData()>item:
                stop=True
            else:
                previous=current
                current=current.getNext()
        temp=Node(item)
        if previous==None:
            temp.setNext(self.head)
            self.head=temp
        else:
            previous.setNext(temp)
            temp.setNext(current)

链表实现复杂度取决于是否需要遍历，isEmpty是1，size是n，search/remove/add有序是n，add无序是1
Python的List是用顺序存储来实现的，并进行了优化

线性结构小结

线性结构小结：
栈Stack维持了数据项后进先出的次序
队列Queue维持了数据项先进先出的次序
双端队列Deque同时具备栈和队列的功能
链表实现的列表List维持相对位置的数据集，节点保存相对位置
有序列表OrderedList
无序列表UnorderedList

涉及到其他知识点：表达式风格，现实问题建模的概念等。