单链表
在闭关刷了几天的leetcode后，我发现了一个事情，就是海贼王真好看，单刷leecode太无聊了，于是乎我边刷题边看海贼王，也是这就是我效率很低的原因，刷了一些题后也相应的去看一下别人说的如何刷才是有效率的，所以现在来记录一下关于链表的实现。
链表是什么：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。-------摘自百度百科
通俗的讲，链表不像list或者数组那样，但是却能实现那样的功能。
为什么用链表？
如果我们用list的话，要在中间插入一个数字，比如在[1,3]中插入一个2，只需要把3换成2，再添加3，如果很长的list呢，很复杂了，但是用链表的话，就很简单了，把前一个指向到要插入的，再插入的这个指向之前的下一个。
创建链表第一步初始化结点类：
class Node:
def __init__(self,item):
self.val = item
self.next = None然后再初始化链表类：
class listnode:
def __init__(self):
self.head =0
def is_empty(self):
return self.head == 0 #判断这个链表是不是空链表
def initlist(self, data): #初始化链表，并传入节点数据
self.head = Node(data[0])
p = self.head #这里的p是一个Node类型的数据，用for传入数据和指针域
for i in data[1:]:
node = Node(i)
p.next = node
p = p.next然后再添加一些增删改查的函数，就算是创建完成一个简单的链表了。
从后面增加一个数据：
def append(self, item):
q = Node(item)
if self.head == 0:
self.head = q
else:
p = self.head
while p.next != None:
p = p.next
p.next = q查看链表的长度：
def getlen(self):
p = self.head
len = 0
while p != 0:
len+=1
if p.next == None:
break
else:
p = p.next
return len删除链表某个数据：
def delete(self,index):
if self.is_empty() or index<0 or index>self.getlen():
print('链表为空')
else:
if index == 0:
self.head = self.head.next
else:
j = 0
n = self.head
p = self.head
while n.next and j<index:
p = n
n = n.next
j+=1
if j == index:
p.next = n.next修改链表的数据：
def uadate(self,index,data):
if self.is_empty() or index<0 or index>self.getlen():
print('链表为空')
else:
p = self.head
j = 0
while p.next and j<index:
p = p.next
j+=1
if j== index:
p.val = data查看链表某个的值：
def getitem(self, item):
if self.is_empty():
print('Linklist is empty.')
return
j = 0
p = self.head
while p.next != 0 and j < item:
p = p.next
j += 1
if j == item:
return p.val
else:
print 'target is not exist!'遍历一遍链表的值：
def traver(self):
if self.is_empty():
print('链表为空')
else:
p = self.head
while p.next:
print(p.val)
p = p.next链表中插入数值：
def insert(self,index,data):
if self.is_empty() or index<0 or index>self.getlen():
print('链表为空')
else:
if index == 0:
q = Node(data,self.head)
self.head = q
else:
j = 0
pst = self.head
p = self.head
while p.next and j<index:
pst = p
p = p.next
j+=1
if index == j:
q = Node(data)
pst.next = q
q.next = p主要靠理解，其次靠理解，第三还是要靠理解。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-08-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
