链表是线性表的链式存取的数据结构，是一种链式存取的数据结构，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：数据域（数据元素的映象）+ 指针域（指示后继元素存储位置），数据域就是存储数据的存储单元，指针域就是连接每个结点的地址数据。 相比于线性表顺序结构，操作复杂。
class Node:
def __init__(self,item):
self.item=item
self.next=None
a=Node(1)
b=Node(2)
c=Node(3)
a.next=b
b.next=c
print(a.next.item)
print(a.next.next.item)
print(a.next.next.next.item)
2
3
Traceback (most recent call last):
File "D:pycharm作业数据结构与算法数据结构链表单链表.py", line 13, in
print(a.next.next.next.item)
AttributeError: 'NoneType' object has no attribute 'item'
a的下一个节点是b,b的下一个节点是c,再往后就是空，会报一个'NoneType'的错误
创建链表
头插法
在2的前面插入3
class Node:
def __init__(self,item):
self.item=item
self.next=None
def create_linklist_head(li):
head=Node(li[0])
for element in li[1:]:
node=Node(element)
node.next=head
head=node
return head
def print_linklist(lk):
while lk:
print(lk.item,end=' ')
lk=lk.next
lk=create_linklist_head([1,2,3])
print_linklist(lk)
尾插法
在2后面插入3
class Node:
def __init__(self,item):
self.item=item
self.next=None
def create_linklist_tail(li):
head=Node(li[0])
tail=head
for element in li[1:]:
node=Node(element)
tail.next=node
tail=node
return head
def print_linklist(lk):
while lk:
print(lk.item,end=' ')
lk=lk.next
lk=create_linklist_tail([1,2,3])
print_linklist(lk)
链表节点的插入
再插入的时候，必选先把4跟2连起来，然后再将1跟4连起来，如果先将4和1连起来，那么1和2之间的连接就没了，2将游离在内存当中，最后被销毁。
链表的删除
p.next=curNode.next curNode.next=p
在删除的时候我们必须先将1与2相连，如果4先删去2就找不到了
p=curNode.next curNode.next=curNode.next.next del p #其实可有可无，因为1与2相连后，4就会丢失
