一、链表和数组

在编写代码中,我们储存的数据是存储于内存当中,内存就像一块块并列排序的小方盒,每个小方盒都有自己地址,我们储存的数据就在这样一个个小方盒当中。

                链表(python)-LMLPHP

这些数据存放的结构有两种基本方式,数组和链表。

1,数组

数组在内存中是按顺序,内存地址来存储的,就好似上图的抽屉,从上到下,按顺序存放物品。这一特征也就意味着数据在内存中是相连的,紧紧不分开的,小的内存空间可能会装不下较多的数据,造成了内存空间浪费。

世界上许多事情有好有坏,有利有弊,数组也是如此,数据在内存中紧密相连,也就意味着牵一发而动全身,比如你想在数组中添加一项数据,这就好比一排已经排好队的士兵,每个人都有自己的编号,而此时你突然要插入其中。

你:“兄弟方便让个位置吗?”

你后面的士兵都一脸凶神恶煞地看着你,如果不是排长强力要求你插入其中,他们肯定不会让你入队,因为你的入队,让你身后的士兵的编号都要往后挪。

数组也是一样,当新加入一个数据时,这就意味着它后面的数据内存地址都要往后稍一稍,删除亦如此。

链表(python)-LMLPHP

2,链表 和赋值原理

链表和在内存中排列整齐的数组不同,它们像一堆散兵游勇,散布于内存中,只要哪里有空隙就往哪里钻,链表高效地运用了内存空间。虽然它们看起来杂乱无章,但其实它们井然有序,暗号让它们紧紧相连。数据与数据之间有一条“暗号”的链子相连接,那个数据在首位,那个数据在第二位……在末尾都非常清楚。

这种“暗号”其实就是内存地址,如下图,长方形就是节点,一个节点包含了两个方面的内容,数据和“暗号”,这个“暗号”其实就是下一个节点的引用信息。

链表(python)-LMLPHP

链表的第一个和最后一个节点最重要和最特殊,最后一个节点则意味着后面没有数据了,所以它指向None,第一个节点的内存地址需要一个地方来保存,所以设立一个head属性对第一个节点应用。

下面来实现节点代码,一个节点需要存放数据和对下一个数据的引用:

class Node:
def __init__(self,x):
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
 

相信很多人都有疑问,为什么把下一个节点赋给上一个节点的next就实现了内存的引用呢?这与Python的特性有关,Python没有专门的指针,所有变量即是指针。

举一个例子,a = 6,一个简单的赋值,它在内存中是怎样实现的呢?

链表(python)-LMLPHP

首先在内存中会创建数据6,数据6在内存中有自己的内存地址,然后再把变量标签a指向6,如上图a这个长方形中,实际是数据6的内存地址。再比如,a,b = b,a,  这实际就是a指向原来b指向的地址,b指向原来a指向的地址。明白了内存中赋值的原理,那么对Python链表中,next  = 下一个节点,就会很清晰了,next指向下一个节点的内存地址。

三,单链表的实现

1,链表的优点和缺点

链表插入和删除数据非常快,但读取数据非常慢

数组的读取非常快,因为它在内存中连续存储,插入和删除慢,是因为插入和删除都要改变相应的内存地址。

链表的插入和删除都很快,因为只要相应的改变节点中next的指向即可,链表访问一个特定数据时,必须沿着链表一个一个数据访问,所以读取很慢、

2,链表的方法

from node import Node
class UnorderedList:

    def __init__(self):
        self.head = None

    def add(self,item): #添加数据
        temp = Node(item)
        temp.setNext(self.head) #next指向表头,head为引用表头的信息
        self.head = temp  #在把head指向新增加的节点

    def size(self):  #返回链表的size
        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):   #删除某个数据
        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())
08-11 07:13