python实现链表，,链表：链表不需要在内

python实现链表，,链表：链表不需要在内

链表：

链表不需要在内存存储一个连续的地方，通常就像一个链一样

它的每个节点包含本身和下一个元素的地址，以此来把两个元素进行关联，这就是一个链表

链表分单项和双向，一般单项就够用了。

链表存在的用意义：

链表是一个存储的数据结构，C语言中存数据用的是数组，存储所有的元素都是在内存中，每一个元素在内存中相连的位置，如果想删除一个元素，那么后边所有的元素都要向前移动一个位置，这样就提高了时间复杂度，如果是链表里的元素，如果删了一个数，那么把前一个的元素指向被删除元素的后一个元素就可以了，时间复杂度是O(1)，数组里面的时间复杂度是O(n),效率不一样，所以这是链表存在的意义，比数组操作的效率高。

用于C语言中代替数组存储数据，效率会高一些

但是在python中直接用list就可以

链表里是用指针指向下一个元素的地址，但是python里没有指针，那就

用变量存一下下一个元素的地址,代替指针

链表定义：

链表可以用类的实例表示，实例有value和next属性，next指向下一个实例

定义节点

class p():pass

实例化一个实例，用a来执行它

a=P()

a指向P类的一个实例的地址

self.next=P()，指向下一个元素

最后一个元素的下一个指针域指向None

数据域 指针域（下一个节点的地址）

最后一个元素的指针域是None就结束了

定义节点类：

代码：

#encoding=utf-8

class Node:

def __init__(self,value=None,next=None):#next(指针域)

self.value=value

self.next=next

n1=Node(1)

n2=Node(2)

n3=Node(3)

n1.next=n2

n2.next=n3

print "n1.value:",n1.value

print "n2.value:",n2.value

print "n2.value:",n3.value

print "######################"

print "n1.next.value:",n1.next.value

print "n2.next.value:",n2.next.value

print "n3.next:",n3.next

结果：

定义函数 打印出所有节点的值：

使用while循环判断，节点.next是否为空，不空，就打印

def printLinkedList(node):

while True:

if node.next != None:

print node.value

else:

print node.value

break

node = node.next#从当前节点跳到下一个节点

printLinkedList(n1)

原理：判断最后一个元素的值是不是None

结果：

或者：

代码：

def printLinkedValue(node):

while node is not None:

print node.value

node = node.next

return ""

print printLinkedValue(n1)

结果：

D:\>python test.py

1

2

3

递归方式正序输出：

代码：

def printLinkedList(node):

#递归

#自己调用自己，并且有结束的条件，这是递归的原则

if node.next is None:

print node.value

return

print node.value

printLinkedList(node.next)

#return ""

printLinkedList(n1)

结果：

D:\>python test.py

1

2

3

拆解：

n1:1
printLinkedList(n2)
n2:2
printLinkedList(n3)
n3:3

递归方式逆序输出

def printReversedLinkedList(node):

if node.next is None:

print (node.value)

return

printReversedLinkedList(node.next)

print (node.value)

return None

printReversedLinkedList(n1)

结果：

n1-->n2--n3(打印3，返回)---打印一个2---》1

递归逆序图解：

递归的时候是往回捣~~

相当于每次执行递归时，记个账本，最后一点点往前算账~~

链表类：

练习代码：

class LinkedList(object):

def __init__(self,head=None):

self.head = head

#重写__len__函数计算链表长度

def __len__(self):

count = 0

if self.head == None:

print "b"*10

return count

print "c"*10

node =self.head

print "d"*10

while node:

print "e"*10

count +=1

node = node.next

print "f"*10

return count

a=LinkedList(n1)

print len(a)

结果：

D:\>python test.py

cccccccccc

dddddddddd

eeeeeeeeee

ffffffffff

eeeeeeeeee

ffffffffff

eeeeeeeeee

ffffffffff

3

在链表末尾加入一个节点：

练习代码：

def append(self,node):

if self.head == None:

self.head = node

return node

cur_node = self.head

while cur_node.next != None:

print cur_node.value

cur_node = cur_node.next

cur_node.next=node

return cur_node.value

结果：

D:\>python test.py

1

2

3

4

4

查找一个节点：

练习代码：

def find(self,value):

if self.head == None:

return

cur_node = self.head

while cur_node:

if cur_node.value == value:

print cur_node.value

return cur_node

else:

cur_node = cur_node.next

a=LinkedList(n1)

print a.find(3)

结果：

D:\>python test.py

3

<__main__.Node object at0x00000000058F5D30>

插入一个节点：

练习代码：

def insertFront(self,data):

if self.head == None:

self.head = Node(data)

return self.head

else:

tmp = self.head

self.head=Node(data)

self.head.next = tmp

return self.head

a=LinkedList(n1)

print a.insertFront(5)

print a.insertFront(5).value

结果：

D:\>python test.py

<__main__.Node object at0x00000000055A5EB8>

5

删除列表中的某个值对应的节点：

练习代码：

def delete(self,value):

if self.head==None:

return None

elif self.head.value == value:

self.head = self.head.next

else:

fro_node = None

cur_node = self.head

while cur_node:

if cur_node.value != value:

fro_node=cur_node

cur_node = cur_node.next

else:

fro_node.next =cur_node.next

return cur_node.value

return None

a=LinkedList(n1)

print a.delete(3)

结果：

D:\>python test.py

3

获取有所节点的值：

练习代码：

def get_all(self):

list=[]

if self.head == None:

return None

else:

cur_node = self.head

while cur_node:

list.append(cur_node.value)

cur_node = cur_node.next

return list

a=LinkedList(n1)

print a.get_all()

结果：

D:\>python test.py

[1, 2, 3]

所有练习代码:

#encoding=utf-8

class Node(object):

def __init__(self,value=None,next=None):

self.value=value

self.next=next

n1=Node(1)

n2=Node(2)

n3=Node(3)

n1.next=n2

n2.next=n3

class LinkedList(object):

def __init__(self,head=None):

self.head = head

def __len__(self):

count = 0

if self.head == None:

return count

node =self.head

while node:

count +=1

node = node.next

return count

def append(self,node):

if self.head == None:

self.head = node

return node

cur_node = self.head

while cur_node.next != None:

print cur_node.value

cur_node = cur_node.next

cur_node.next=node

return cur_node.value

def find(self,value):

if self.head == None:

return

cur_node = self.head

while cur_node:

if cur_node.value == value:

print cur_node.value

return cur_node

else:

cur_node = cur_node.next

def insertFront(self,data):

if self.head == None:

self.head = Node(data)

return self.head

else:

tmp = self.head

self.head=Node(data)

self.head.next = tmp

return self.head

def delete(self,value):

if self.head==None:

return None

elif self.head.value == value:

self.head = self.head.next

else:

fro_node = None

cur_node = self.head

while cur_node:

if cur_node.value != value:

fro_node=cur_node

cur_node = cur_node.next

else:

fro_node.next =cur_node.next

return cur_node.value

return None

def get_all(self):

list=[]

if self.head == None:

return None

else:

cur_node = self.head

while cur_node:

list.append(cur_node.value)

cur_node = cur_node.next

return list

a=LinkedList(n1)

print a.get_all()

python实现链表