链表
链表
链表的实现
数据区+链接区
链接区,下一个节点的位置
单链表操作
is_empty() 链表是否为空
length() 链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos,item) 指定位置添加元素
search(item) 查找节点是否存在
单链表结点
python交换两个变量
a = 10 //产生一个变量 a 把 10放在里面
b = 20
a,b = b,a
地址指向
指向的地址。
a = 10
// a 代表的是内存,它内存中保存的是一个地址,地址指向什么,a的变量就是谁的
PYthon
变量的本质
python基础(5):深入理解 python 中的赋值、引用、拷贝、作用域
结点串到链表上。
两个类,链表类和结点类。
这两个类之间的关系。
为空
def is_empty(self):
#链表是否为空,self对象属性
return self._head == None #返回和None的值,相等就为空,true
长度
链表中存在多少个结点。
current 指针,当前的位置。
def length(self):
#链表长度
# cur 游标,用来移动遍历节点
cur = self._head #指向起始节点
# count 记录数量
count = 0
while cur != None: #判断最后的位置 cur.next == None
count += 1
cur = cur.next
return count
遍历
def travel(self):
#遍历整个链表
cur = self._head
while cur != None:
print cur.elem
cur = cur.next
头部添加结点
一开始
def add(self, item):
# 链表头部添加元素 头插法
# 插入的新节点的next 指向 _head 指向的 next,然后 head 指向插入的新节点
# 考虑空链表
node = Node(item) #初始化一个节点
node.next = self._head
self._head = node
指定位置添加
def insert(self,pos,item):
#指定位置添加元素
# pos 参数 from 0 insert(2,400) node(400)
# pre ,指定位置的前一个元素
if pos < 0:
# 设置为头插法
self.add(item)
elif pos > self.length()-1:
#设置尾部添加
self.append(item)
else:
pre = self._head # 指向的结点,赋予 pre
count = 0
while count < (pos-1):
count = count + 1
pre = pre.next
#循环退出后,pre 指向 pos -1
node = Node(item)
node.next = pre.next
pre.next = node
测试
ll.append(1)
print ll.is_empty()
print ll.length()
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
# 8 1 2 3 4
ll.insert(-1,9)
ll.travel()
ll.insert(3,10)
ll.travel()
ll.insert(14, 12)
ll.travel()
结果
True
0
False
1
9 8 1 2 3 4
9 8 1 10 2 3 4
9 8 1 10 2 3 4 12
查找
一个游标从头结点开始,进行比对。
def search(self,item):
# 查找节点是否存在
cur = self._head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
代码
# -*- coding:utf-8 -*-
__author__ = '504'
__date__ = '2018/4/24 14:36'
class Node(object):
# 结点类
def __init__(self, elem):
# 构造函数初始化 item
self.elem = elem # 结点一个属性,保存数据
self.next = None # 结点位置初始为空,链接域为空
class SingleLinkList(object):
# 链表
def __init__(self,node=None): # 构造函数
self._head = node # 私有属性,初始化
def is_empty(self):
# 链表是否为空,self对象属性
return self._head == None #返回和None的值,相等就为空,true
def length(self): # 链表长度
# cur 游标,用来移动遍历节点
cur = self._head
# 指向头节点
# count 记录数量
count = 0
while cur != None: # 判断最后的位置 cur.next == None
count += 1
cur = cur.next
return count
def travel(self):
# 遍历整个链表
cur = self._head
while cur != None:
print cur.elem,
cur = cur.next
print ""
def add(self, item):
# 链表头部添加元素 头插法
# 插入的新节点的next 指向 _head 指向的 next,然后 head 指向插入的新节点
# 考虑空链表
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 # None
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self,pos,item):
#指定位置添加元素
# pos 参数 from 0 insert(2,400) node(400)
# pre ,指定位置的前一个元素
if pos < 0:
# 设置为头插法
self.add(item)
elif pos > self.length()-1:
#设置尾部添加
self.append(item)
else:
pre = self._head # 指向的结点,赋予 pre
count = 0
while count < (pos-1):
count = count + 1
pre = pre.next
#循环退出后,pre 指向 pos -1
node = Node(item)
node.next = pre.next
pre.next = node
def remove(self, item):
# 删除节点
# pre.next = cur.next
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
if __name__ == "__main__":
ll = SingleLinkList() # 构造对象
print ll.is_empty()
print ll.length()
ll.append(1)
print ll.is_empty()
print ll.length()
ll.append(2)
ll.add(8)
ll.append(3)
ll.append(4)
# 8 1 2 3 4
ll.insert(-1,9)
ll.travel()
ll.insert(3,10)
ll.travel()
ll.insert(14, 12)
ll.travel()
ll.remove(12)
ll.travel()
结果
True
0
False
1
9 8 1 2 3 4
9 8 1 10 2 3 4
9 8 1 10 2 3 4 12
9 8 1 10 2 3 4
Process finished with exit code 0
实现无序列表:链表
Implementing an Unordered List: Linked Lists
一些项被随机的放置,如果在每一项中保持一些明确的信息,即下一项的位置。每个项的相对位置可以通过简单地从一个项到下一个项的链接来表示。
指定链表中的第一个位置,一旦知道第一项在哪里,第一项可以告诉我们第二项是什么。外部引用通常被称为链表的头,最后一项需要知道没有下一项。
Node 类
链表实现的基本构造是节点。每个节点对象必须保存两个信息,节点必须包含列表项本身,将这个称为节点的数据字段。每个节点必须保存对下一个节点的引用。
要构造一个节点,需要提供该节点的初始数据值。
#!/usr/bin/python
# -*- coding:utf-8 -*-
class Node:
def __init__(self,initdata):
self.data = initdata #初始化
self.next = None # None 在 Node类和链表本身发挥重要作用,引用None代表没有下一个节点
def getData(self):
return self.data #获取该位置值
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
class UnorderedList:
def __init__(self):
self.head = None
temp = Node(93)
print temp.getData()
赋值语句将产生一个包含值93的节点对象。
会用下图表示一个节点对象。Node类还包括访问、修改数据和访问下一个引用的常用方法。
Unordered List 类
无序列表将从一个节点构建,每个节点通过显示引用链接到下一个节点。