Python 列表与链表的区别详解

class node:
	def __init__(self, value, next=None):	
		self.value = value		
		self.next = next

>>> L = Node("a", Node("b", Node("c", Node("d"))))
>>> L.next.next.value
'c'

按元素值查找:
     按顺序查找，复杂度是一样的。
     按二分查找，链表没法查找.
按下标查找:
     列表是O( 1 )
     链表是O(n)
在某元素后插入:
     列表是O(n)
     链表是O( 1 )
删除某元素:
     列表是O(n)
     链表是O( 1 )

# 节点定义：
class  Node( object ):     
　　 def  __init__( self ,item):
	     self .item  =  item  # 数据域
	     self . next  =  None  # 指针域
 
n1  =  Node( 1 )
n2  =  Node( 2 )
n3  =  Node( 3 )
 
n1. next  =  n2
n2. next  =  n3
# 通过 n1 找到n3的值
print (n1. next . next .item)

# 节点定义：
class  Node( object ):     
　　 def  __init__( self ,item):
	     self .item  =  item  # 数据域
	     self . next  =  None  # 指针域
 
n1  =  Node( 1 )
n2  =  Node( 2 )
n3  =  Node( 3 )
 
n1. next  =  n2
n2. next  =  n3
# 通过 n1 找到n3的值
print (n1. next . next .item)

p  =  Node( 5 )  # 要插入的值
curNode  =  Node( 1 )  # 标志位
# 顺序不能乱，否则就找不到原链表中的下一个值
p. next  =  curNode. next  # 指定插入值之后的值为标志位之后的值
curNode. next  =  p   # 然后再把原先的链next指向改成插入的值

curNode 代表当前值
p  =  curNode. next  # 表示要删除的数
curNode. next  =  p. next  # 重新指定建立链表
del  p 删除数

def  createLinkListF(li):
　　l  =  Node()  # 始终指向头节点
　　 for  num  in  li:
     s  =  Node(num)
     s. next  =  l. next
     l. next  =  s
　　 return  l

def  createLinkListR(li):
　　l  =  Node()
　　r  =  l  # r指向尾节点
　　 for  num  in  li:
     s  =  Node(num):
     r. next  =  s
     r  =  s  # 重新指定尾节点

class  Node( object ):
　　 def  __init__( self ,item = None ):
     self .item  =  item    # 记录当前值
     self . next  =  None    # 记录下一个值
     self .prior  =  None   # 记录前置的一个值

curNode  =  Node( 1 )  # 取一数据作为标志位

p  =  Node( 2 )  # 要插入的数
p. next  =  curNode. next  # 指定插入数的next 是 当前数的next
curNode. next .prior  =  p  # 指定插入数的下一个数的 前置数为当前的数值
p.prior  =  curNode  # 插入数的前置数为 标志位
curNode. next  =  p  # 指定，标志位的next数是当前要插入的数

p  =  curNode. next  # 标志位的下一个数，要删除的数
curNode. next  =  p. next  # 将next指向下一个数
p. next .prior  =  curNode # 将要删除数的下一个数的前置数改为标志位
del  p  # 删除当前数

尾插法：
def  createLinkListR(li):
　　l  =  Node()
　　r  =  l
　　 for  num  in  li:
     s  =  Node(num)
     r. next  =  s
     s.prior  =  r
     r  =  s
　　 return  l,r
 

# 创建节点 
class  Node( object ):
     
     def  __init__( self ,item = None , next = None ):
         self .item  =  item  # 数据域
         self . next  =  next  # 指针域 
 
# 循环逆置方法
def  revLinkList(link):
     
     if  link  is  None  or  link. next  is  None :
         return  link
         
     pre  =  link  # 记录当前节点的值
     cur  =  link. next  # 记录下一节点的值
     pre. next  =  None  # 先将当前节点的next指向定为None
     
     while  cur:  # 链表中一直有值
         tmp  =  cur. next  # 获取cur的下一个值，临时赋值给tmp
         cur. next  =  pre  # 将cur值指向pre
         pre  =  cur  # 重新指定
         cur  =  tmp
     
     return  pre  # 把当前值返回
 
#应用
link  =  Node( 1 , Node( 2 , Node( 3 , Node( 4 , Node( 5 , Node( 6 , Node( 7 , Node( 8 , Node( 9 )))))))))
r  =  revLinkList(link):   # 链表逆置之后，得到的head值
while  r:
     print ( "{0}---->" . fORMat (r.item))  # 输出逆置后的当前值
     r  =  r. next  # 获取下一个，重新赋给r，然后交给上边输出

基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)；为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。
允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时 list 对象的标识 id 不变，只能采用分离式实现技术。

class Node(object):
    """节点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        """链表是否为空"""
        return self.__head == None

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

    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("")

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

    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

    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

    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
                break
            else:
                pre = cur
                cur = cur.next

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