数据结构 之 链表
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表
单向链表
单向链表又称单链表，是链表中最简单的一种形式，他的每个节点包含两个域，一个是信息域（元素域），一个事链接域
这个链接指向的链表的下一个节点，而最后的一个节点链接域则指向空
基本操作：
代码实现 (python)：
1. 创建结点
class Node(object): """结点""" def __init__(self,item): self.item = item self.next = None
2. 创建链表
class SingleList(object): """单链表""" def __init__(self,node=None): self._head = node
3. 基本操作
def is_empty(self): """链表是否为空""" return self._head == None def length(self): """链表长度""" cur = self._head count = 0 if cur is not None: while cur.next: count+=1 cur = cur.next count += 1 # 补上最后一个节点数量。 return count # cur = self._head # count = 0 # while cur != None: # count += 1 # cur = cur.next # return count def traval(self): """遍历整个链表""" cur = self._head while cur!= None: print(cur.item) cur = cur.next print('*'*30) def add(self,item): """头部添加元素""" # node = Node(item) # if self.is_empty(): # self._head = node # else: # oldnode = self._head # self._head = node # node.next = oldnode # 简化： 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 start is 0 """ if pos < 0: self.add(item) # 头插法 elif pos > self.length()-1: self.append(item) # 尾插法 else: node = Node(item) pre = self._head count = 0 while count < (pos - 1): # pos- 1 移动前一位置,对前一节点进行操作 count += 1 pre = pre.next # 当循环退出后，pre 指向pos-1位置 node.next, pre.next = pre.next, node def remove(self,item): """删除节点""" cur = self._head pre = None while cur!=None: if cur.item == item: # 判断是不是在头节点删除 if cur is self._head: # pre is None or cur is self._head self._head = cur.next else: pre.next = cur.next break pre = cur cur = cur.next def search(self,item): """查找元素""" cur = self._head while cur!=None: if cur.item == item: return True cur = cur.next return False
#encoding:utf-8 # __author__ = 'donghao' # __time__ = 2019/3/15 21:39 # a = 10 # b = 20 # c = 30 # print(id(a)) # print(id(b)) # print(id(c)) # a,b,c = b,c,a # print('改变后 a ',id(a)) # print('改变后 b ',id(b)) # print('改变后 c ',id(c)) class Node(object): """结点""" def __init__(self,item): self.item = item self.next = None class SingleList(object): """单链表""" def __init__(self,node=None): self._head = node def is_empty(self): """链表是否为空""" return self._head == None def length(self): """链表长度""" cur = self._head count = 0 if cur is not None: while cur.next: count+=1 cur = cur.next count += 1 # 补上最后一个节点数量。 return count # cur = self._head # count = 0 # while cur != None: # count += 1 # cur = cur.next # return count def traval(self): """遍历整个链表""" cur = self._head while cur!= None: print(cur.item) cur = cur.next print('*'*30) def add(self,item): """头部添加元素""" # node = Node(item) # if self.is_empty(): # self._head = node # else: # oldnode = self._head # self._head = node # node.next = oldnode # 简化： 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 start is 0 """ if pos < 0: self.add(item) # 头插法 elif pos > self.length()-1: self.append(item) # 尾插法 else: node = Node(item) pre = self._head count = 0 while count < (pos - 1): # pos- 1 移动前一位置,对前一节点进行操作 count += 1 pre = pre.next # 当循环退出后，pre 指向pos-1位置 node.next, pre.next = pre.next, node def remove(self,item): """删除节点""" cur = self._head pre = None while cur!=None: if cur.item == item: # 判断是不是在头节点删除 if cur is self._head: # pre is None or cur is self._head self._head = cur.next else: pre.next = cur.next break pre = cur cur = cur.next def search(self,item): """查找元素""" cur = self._head while cur!=None: if cur.item == item: return True cur = cur.next return False single_obj = SingleList() #初始化链表 single_obj.append('123') single_obj.append(400) print(single_obj.is_empty()) print(single_obj.length()) single_obj.traval() single_obj.add('add head 1000') single_obj.add('add head 2000') single_obj.add('add head 3000') print(single_obj.is_empty()) print(single_obj.length()) single_obj.traval() single_obj.insert(-1,'插入节点') single_obj.insert(5,'大于长度插入节点') single_obj.traval() print(single_obj.search('123')) single_obj.remove('add head 2000') single_obj.traval() single_obj.append('123') single_obj.traval() single_obj.remove('1236') single_obj.traval()
View Code
双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表
class Node(object): def __init__(self,item): self.item = item self.next = None self.prev = None
双链表 判断是否为空，链表长度，遍历链表都跟单链表一致，直接继承就好了
class DoubleLinkList(SingleList): """双链表""" def add(self,item): """头部添加元素""" node = Node(item) node.next = self._head self._head = node node.next.prev = 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 node.prev = cur def insert(self,pos,item): """指定位置添加元素 :param pos start is 0 """ if pos < 0: self.add(item) # 头插法 elif pos > self.length()-1: self.append(item) # 尾插法 else: node = Node(item) cur = self._head count = 0 while count < pos: count += 1 cur = cur.next node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node def remove(self,item): """删除节点""" cur = self._head while cur!=None: if cur.item == item: # 判断是不是在头节点删除 if cur is self._head: # pre is None or cur is self._head self._head = cur.next if cur.next: # 判断链表是否就一个结点 cur.next.prev = None # 结点 置空 else: cur.next.prev = cur.prev if cur.next: # 判断是否为最后一个结点 cur.prev.next = cur.next break cur = cur.next def search(self,item): """查找元素""" cur = self._head while cur!=None: if cur.item == item: return True cur = cur.next return False
#encoding:utf-8 # __author__ = 'donghao' # __time__ = 2019/3/16 13:23 from 数据结构.链表.Single import SingleList class Node(object): def __init__(self,item): self.item = item self.next = None self.prev = None class DoubleLinkList(SingleList): """双链表""" def add(self,item): """头部添加元素""" node = Node(item) node.next = self._head self._head = node node.next.prev = 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 node.prev = cur def insert(self,pos,item): """指定位置添加元素 :param pos start is 0 """ if pos < 0: self.add(item) # 头插法 elif pos > self.length()-1: self.append(item) # 尾插法 else: node = Node(item) cur = self._head count = 0 while count < pos: count += 1 cur = cur.next node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node def remove(self,item): """删除节点""" cur = self._head while cur!=None: if cur.item == item: # 判断是不是在头节点删除 if cur is self._head: # pre is None or cur is self._head self._head = cur.next if cur.next: # 判断链表是否就一个结点 cur.next.prev = None # 结点 置空 else: cur.next.prev = cur.prev if cur.next: # 判断是否为最后一个结点 cur.prev.next = cur.next break cur = cur.next def search(self,item): """查找元素""" cur = self._head while cur!=None: if cur.item == item: return True cur = cur.next return False
View Code
插入示例：
链表和顺序表区别：
版权声明：本文为donghaoblogs原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。