数据结构——链表&双链表的python实现

ゞ浴缸里的玫瑰 2023-02-14 02:42 107阅读 0赞

### 链表的python实现 ###

*   *  单链表的实现
     *  双链表的实现

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70]

## 单链表的实现 ##

#定义单链表节点类
    class Node(object):
        def __init__(self,value=None,next=None):
            self.value = value
            self.next = next
    
    #单链表结构类
    class LinkedList(object):
        def __init__(self):			#初始化链表的头节点以及链表的长度
            self.head = Node()
            self.length = 0
        def __len__(self):			#返回链表的长度
            return self.length
    
    	#定义尾插节点方法
    	def append(self,value):		#添加节点，从末尾处添加
            node = Node(value)
            if self.length==0:
                self.head.next=node
                self.length += 1
            else:
                curnode = self.head.next
                while curnode.next!=None:
                    curnode = curnode.next
                curnode.next=node
                self.length += 1
                
    	#定义链表开始处添加
    	def start_insert(self,insert_value):#在开始处插入
            node = Node(insert_value)
            if self.length==0:
                self.head.next = node
            else:
                tmp_node=self.head.next
                self.head.next = node
                node.next = tmp_node
            self.length +=1
    
    	#定义在链表任意处添加节点
    	def insert(self,location,value):#在任意位置插入节点
            node = Node(value)
            if self.length==0:
                self.head.next = node
                self.length += 1		#插入一个节点，链表长度加1
            else:
                for nd in self.iter_node():
                    if nd.value == location:
                        tmp_node = nd.next
                        nd.next = node
                        node.next = tmp_node
                        self.length += 1
                        return True
                return False			#返回False，未找到插入位置
    
    	#定义遍历链表方法
    	def __iter__(self):				#遍历链表节点
        	for node in self.iter_node():
            	yield node.value
            	
    	def iter_node(self):
        	curnode = self.head.next
        	while curnode.next !=None:
            	yield curnode
            	curnode = curnode.next
        	if curnode.next == None:
            	yield curnode
    
    	#定义搜索节点方法(按照节点的value搜索)
    	def search(self,value):		#搜索节点
        	index = 1
        	if self.length==0:		#如果长度为0，则表示链表结构中只有一个头节点
            	return -1			#返回-1，表示不存在该节点
        	else:
            	for node in self.iter_node():
                	if node.value == value:
                    	return index #搜索到节点的序号
                	index += 1
            	return -1			#未搜索到节点
            	
    	#定义删除节点的方法
    	def del_node(self,del_value):#删除节点
        	Flag = False
        	if self.length==0:
            	return Flag
        	else:
            	previous_node = self.head
            	for curnode in self.iter_node():
                	if curnode.value == del_value:
                    	previous_node.next=curnode.next
                    	del curnode
                    	self.length -= 1
                    	Flag = True
                	else:
                    	previous_node = curnode
            	return Flag

## 双链表的实现 ##

#定义节点类
    class Node(object):
        def __init__(self,value=None,prev=None,next=None):
            self.value = value
            self.prev = prev
            self.next = next
    
    #定义双链表类
    class Double_LinkedList(object):
        def __init__(self):#初始化双链表只有一个头结点，它的前向指针和后向指针都指向自己，长度为0
            node = Node()
            node.prev = node
            node.next = node
            self.head = node
            self.length = 0
            
        def __len__(self):
            return self.length
            
        def headnode(self):				#获取第一个节点
            return self.head.next
            
        def tailnode(self):				#获取最后一个节点
            return self.head.prev
            
        def append(self,value):			#添加节点，从末尾添加
            node = Node(value)
            tail_node = self.tailnode()
            tail_node.next = node
            node.prev = tail_node
            node.next = self.head
            self.head.prev = node
            self.length += 1
    
    	def head_append(self,value):	#添加节点，从头添加
            node =Node(value)
            if self.head.next is self.head:
                node.next = self.head
                node.prev = self.head
                self.head.next = node
                self.head.prev = node
            else:
                node.prev = self.head
                head_node = self.headnode()
                self.head.next = node
                head_node.prev = node
                node.next = head_node
            self.length += 1
    
    	def insert(self,index,value):	#在任意位置插入新节点
            node = Node(value)
            i = 1
            if self.length<index:
                raise Exception('out of range')
            if self.head.next is self.head:
                self.head.next = node
                self.head.prev = node
                node.next = self.head
                node.prev = self.head
                self.length += 1
                return True
            else:
                if index==0:
                    self.head_append(value)
                    return True
                for cur_node in self.iter_node():
                    if i == index:
                        next_node = cur_node.next
                        node.prev = cur_node
                        node.next = next_node
                        cur_node.next = node
                        next_node.prev = node
                        self.length += 1
                        return True
                    i += 1
    	
    	def del_node(self,index):	#删除节点
            i=1
            for cur_node in self.iter_node():
                if i == index:
                    next_node=cur_node.next
                    prev_node=cur_node.prev
                    prev_node.next = next_node
                    next_node.prev = prev_node
    
                    self.length -= 1
                    return True
                i += 1
    
    	def iter_node(self):		#遍历节点
        	if self.head.next is self.head:
            	return -1
        	cur_node = self.head.next
        	while cur_node.next is not self.head:
            	yield cur_node
            	cur_node = cur_node.next
        	yield cur_node
    
    	def __iter__(self):			#遍历节点，输出每个节点的值
         	for node in self.iter_node():
             	yield node.value
    
    	def reverse_iter_node(self):#反向遍历节点
        	if self.head.prev is self.head:
            	return False
        	cur_node = self.head.prev
        	while cur_node.prev is not self.head:
            	yield cur_node
            	cur_node = cur_node.prev
        	yield cur_node

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531161906918.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3,size_16,color_FFFFFF,t_70