python数据结构-单链表

python数据结构-单链表 链表 链表定义

链表(linked list)是一种常见的基础数据结构,是一种线性表，但是不像顺序表-样连续存储数据，而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。

单向链表

        单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

     表元素域elem用来存放具体的数据。

     链接域next用来存放下一一个节点的位置(python中的标识)   

     变量p指向链表的头节点(首节点)的位置，从p出发能找到表中的任意节点。

节点实现

class SingleNode(object):
'''单链表的结点'''
    def __init__ ( self,item):
        #_item存放数据元素
        self.item = item
        #_next是下一个节点的标识
        self.next = None

单链表 *** 作

is_ empty() 链表是否为空

def is_ empty(self):
    '''链表是否为空'''
    return self.__head == None

length()链表长度

def length(self):
    '''链表长度'''
    # cur游标， 用来移动遍历节点
    cur = self._head
    # count记录数量
    count = 1
    while cur != None:
        count += 1    
        cur = cur. next
    return count

travel()遍历整个链表

def travel(self):
    '''遍历整个链表'''
    cur = self._head
    while cur != None:
        print(cur.elem)
        cur = cur.next

additem()链表头部添加元素

def add(self, item):
    '''链表头部添加元素，头插法'''
    node = Node(item)
    node.next = self._head
    self._head = node

append(item)链表尾部添加元素

def append(self, item):
    '''链表尾部添加元素 尾插法'''
    node = Node( item)
    if self. is_ empty():
        self._ head = node
    else:
        cur = self.__head
        while cur.next != None: 
            cur = cur. next
        cur.next = node

insert(pos, item)指定位置添加元素

def insert(self, pos, item):
    '''指定位置添加元素
    :param    pos从0开始
    '''
    if pos <= 0:
        self. add(item)
    elif pos > (self. length()-1):
        self. append(item)
    else:
        pre = self._head
        count = 0
        while count < (pos-1) :
            count += 1
            pre = pre. next
        #当循环退出后，pre指向pos-1位置
        node = Node(item)
        node.next = pre.next
        pre.next = node

remove(item)删除节点

def remove(self, item):
    '''删除节点'''
    cur = self._head
    pre = None
    while cur != None:
        if cur.elem == item: 
            #先判断此结点是否是头节点
            #头节点
            if cur == self._ head:
                self.__ head = cur. next
            else:
                pre.next = cur. next
        else:
            pre = cur
            cur = cur.next
    

search(item)查找节点是否存在

def search(self, item):
    '''查找节点是否存在'''
    cur = self.__head
    while cur != None :
        if cur.elem == item:
            return True
        else:
            cur = cur.next
    
    return False

顺序表和链表对比

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种 *** 作复杂度如下

*** 作链表顺序表访问元素O(n)O(1)在头部插入/删除O(1)O(n)在尾部插入/删除O(n)O(1)在中间插入/删除O(n)O(n)

        虽然表面看起来复杂度都是O(n),但是链表和顺序表在插入和删除时进行的是完全不同的 *** 作。链表的主要耗时 *** 作是遍历查找，删除和插入 *** 作本身的复杂度是O(1)。顺序表查找很快，主要耗时的 *** 作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对 *** 作点之后的所有元素进行前后移位 *** 作，只能通过拷贝和覆盖的方法进行。