精华内容
下载资源
问答
  • 数据结构之链表(单向链表、双向链表、单向循环链表、双向循环链表、静态链表、动态链表) 单向链表 概念 单向链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。链表是使用指针进行构造的列表,并且...

    数据结构之链表(单向链表、双向链表、单向循环链表、双向循环链表、静态链表、动态链表)

    单向链表

    概念

    单向链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。链表是使用指针进行构造的列表,并且是由一个个结点组装起来的,因此又称为结点列表。其中每个结点都有指针成员变量指向列表中的下一个结点,head指针指向第一个结点称为表头,而终止于最后一个指向nuLL的指针。

    节点的数据结构

    typedef struct _LINK_NODE  
    {  
        int data;  
        struct _LINK_NODE* next;  
    }LINK_NODE; 
    

    示意图

    在这里插入图片描述

    双向链表

    概念

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

    节点的数据结构

    typedef struct DuLNode
    {
    ElemType data;
    struct DuLNode *prior,*next;
    }DuLNode,*DuLinkList;
    

    示意图

    在这里插入图片描述

    单向循环链表

    概念

    如果把单链表的最后一个节点的指针指向链表头部,而不是指向NULL,那么就构成了一个单向循环链表,通俗讲就是把尾节点的下一跳指向头结点。

    节点的数据结构

    typedef struct _LINK_NODE  
    {  
        int data;  
        struct _LINK_NODE* next;  
    }LINK_NODE; 
    

    示意图

    在这里插入图片描述

    双向循环链表

    概念

    双向链表的每个结点需要连接前一个结点和后一个结点,所以需要定义两个指针域,分别指向前一个结点和后一个结点。LinkedList在jdk1.7(包含)以后采用双向链表

    节点的数据结构

    typedef struct DuLNode
    {
    ElemType data;
    struct DuLNode *prior,*next;
    }DuLNode,*DuLinkList;
    

    示意图

    在这里插入图片描述

    静态链表

    概念

    静态链表是用类似于数组方法实现的,是顺序的存储结构,在物理地址上是连续的,而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的,在做插入和删除操作时不需要移动元素,仅需修改指针。

    动态链表

    概念

    动态链表是用内存申请函数(malloc/new)动态申请内存的,所以在链表的长度上没有限制。动态链表因为是动态申请内存的,所以每个节点的物理地址不连续,要通过指针来顺序访问。

    展开全文
  • 目录一、链表1.1 单向链表1.1.1 单链表的操作1.2 单向循环链表二、链表与顺序表的对比 一、链表 链表:将元素存放在通过链接构造起来的一系列存储块中。在每一个节点(数据存储单元)里存放下一个节点的位置信息...

    一、链表

    • 链表:将元素存放在通过链接构造起来的一系列存储块中。在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。
    • 链表优点:链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。
    • 链表的插入操作一定要先将新节点指向链表位置,才能断开原链表节点重新指向,否则会出现数据错误。

    1.1 单向链表

    • 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域) 和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。
    • 节点:信息域(元素域)、链接域
    • 单向链表结构
      在这里插入图片描述
    1. 表元素域elem用来存放具体的数据。
    2. 链接域next用来存放下一个节点的位置(python中的标识)
    3. 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。
    1.1.1 单链表的操作
    1、创建节点类
    class Node:
        def __init__(self,elem):
            self.elem=elem
            self.next=None # 默认单节点,next为None
            
    2、创建单链表类:
    class SingeLink():
        def __init__(self):
            self.__head=None
    	"""操作1:判断链表是否为空"""
        def is_empty(self):
            if self.__head is None:
                return True
            else:
                return False
    	"""操作2:链表长度"""
        def length(self):
        	# cur初始时指向头节点
            cur = self.__head
            count = 0
            # 当到达尾结点时进入循环,循环内再后移一位就跳出循环了。
            while cur != None:
                cur = cur.next
                count += 1
            return count
        """操作3:循环打印链表的值"""
        def travel(self):
            if self.is_empty():
                return
            cur = self.__head
            while cur != None:
                print(cur.elem, end=',')
                cur = cur.next
        """操作4:在头部添加数据,满足为空的情况"""
        def add(self,item):
            node = Node(item)	# 先创建一个保存item值的节点
            node.next = self.__head		# 将新节点的链接域next指向头节点,即_head指向的位置
            self.__head = node		# 将链表的头_head指向新节点
        """操作5:链表尾部添加元素"""
        def append(self, item):
            node = Node(item)
            if self.is_empty():
                self.__head = node	# 判断为空直接将头节点指向新节点
            else:
                cur = self.__head	# 定义cur指针指向头节点
                # 若不为空,则找到尾部,将尾节点的next指向新节点
                while cur.next != None:
                    cur = cur.next
                cur.next = node	# 若cur.next为空说明是尾结点
        """操作6:指定位置添加元素"""
        def insert(self, pos, item):
            node = Node(item)
            # 若指定位置为头部之前,则在头部插入
            if pos <= 0:
                self.add(item)
             # 若指定位置为尾部之后,则在尾部插入
            elif pos > (self.length()-1):
                self.append(item)
             # 在中间位置插入
            else:
                cur = self.__head
                count = 0
                # 找到插入的前一个位置
                while count < pos-1:
                    count += 1
                    cur = cur.next
                node.next = cur.next	# 先将新节点指向插入位置的节点
                cur.next = node			# 再把插入位置的前一个节点指向新节点
    
        """操作7:删除节点"""
        def remove(self, item):
            cur = self.__head
            pre = None			# 定义一个空节点
            while cur != None:
                if cur.elem == item:	# 找到节点
                    if cur.elem == self.__head:		# 如果是第一个节点,则将头节点指向下一节点
                        self.__head = cur.next
                    else:
                        pre.next = cur.next		# 将删除位置的前一个节点指向删除位置的后一个节点
                    break
                else:
                	# 没找到继续后移:先将当前节点保存在pre中,再后移
                    pre = cur
                    cur = cur.next
        """操作8:查找节点是否存在"""
        def search(self, item):
            cur = self.__head
            while cur != None:		# 循环查找,找到返回True,否则返回False
                if cur.elem == item:
                    return True
                cur = cur.next
            return False
            
    3、校验
    if __name__ == '__main__':
        s = SingeLink()
        print(s.is_empty())
        s.add(10)
        s.add(20)
        s.append(100)
        s.insert(-1, 200)
        s.remove(200)
        print(s.length())
        s.travel()
    
    

    1.2 单向循环链表

    • 单向循环链表中最后一个节点的next域不再为None,而是指向链表的头节点。
    • 单向循环链表的操作:
    1、创建节点类
    class Node:
        def __init__(self, elem):
            self.elem = elem
            self.__head = None
    2、创建链表类
    class SingeLoopLike():
        def __init__(self):
            self.__head=None
    	"""操作1:判断是否为空链表"""
        def is_empty(self):
            if self.__head is None:
                return True
            else:
                return False
    	"""操作2:获取链表长度"""
        def length(self):
            cur = self.__head
            if self.is_empty():
                return 0
            else:
                count = 1
                # 判断节点是否指向头节点,确定尾节点。当循环内移到尾节点时无法进入循环,所以尾节点没有遍历到,count初始值赋值1。
                while cur.next != self.__head:
                    count += 1
                    cur = cur.next
                return count
    	"""操作3:循环打印链表的值"""
        def travel(self):
            cur = self.__head	 
            if self.is_empty():
                return
            while cur.next != self.__head:
            	print(cur.elem)
                cur = cur.next	
            print(cur.elem,end=',')	# 尾节点无法进入循环,所以跳出循环还要打印
    	"""操作4:头部插入"""
        def add(self,item):
            node = Node(item)	# 先创建一个保存item值的节点
            if self.is_empty():
                self.__head = node
                node.next =node		# 为空直接插入后还要自己指向自己
            else:
                node.next = self.__head		# 不为空时新节点指向头节点
                cur = self.__head
                # 找到尾节点
                while cur.next != self.__head:	
                    cur = cur.next
                cur.next = node		# 尾节点指向新节点
                self.__head = node	# 头节点指向新节点
    	"""操作5:尾部添加"""
        def append(self,item):
            node = Node(item)
            cur = self.__head
            if self.is_empty():
                self.add(item)
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node			# 尾节点指向新节点
            node.next = self.__head		# 新节点指向头节点
    	"""操作6:按位置插入"""
        def insert(self,pos,item):
            node = Node(item)
            cur = self.__head
            if pos <= 0:
                self.add(item)
            elif pos > (self.length()-1):
                self.append(item)
            else:
    	        count = 0
    	        # 找到插入位置的前一个节点,跳出循环时cur即为插入前一个节点
    	        while count < pos-1:
    	            count += 1
    	            cur = cur.next
    	        node.next = cur.next	# 新节点指向插入位置节点
    	        cur.next = node			# 插入位置前一个节点指向新节点
    	"""操作7:删除节点"""
        def remove(self,item):
            cur = self.__head
            pre = None
            # 为空返回None
            if self.is_empty():
                return None
            while cur.next != self.__head:
            	# 找出删除节点
                if cur.elem == item:
                	# 情况1:若是删除头节点
                    if cur == self.__head:
                        # self.__head = cur.next
                        rear = self.__head	# 定义一个节点指向头节点
                        # 若不止一个节点,则找到尾节点。跳出循环时rear即为尾节点
                        while rear.next != self.__head:
                            rear = rear.next
                        rear.next = cur.next	# 尾节点指向第二个节点
                        self.__head = cur.next	# head也指向第二个节点‘’
                    # 情况2:如果不是头节点 
                    else:
                        pre.next = cur.next
                    return
                # 没找到指针继续后移
                else:
                    pre = cur
                    cur = cur.next
            if cur.elem == item:
            	# 情况3:如果是头节点且只有一个节点,则head直接指向空
                if pre is None:
                    self.__head = None
                # 情况4:如果删除的是尾节点,则尾节点上一节点指向头节点
                else:
                    pre.next = self.__head
    	# 查找节点
        def search(self,item):
            cur = self.__head
            while cur.next != self.__head:
                if cur.elem == item:
                    return True
                cur = cur.next
             # 跳出循环时尾节点未进入循环判断,所以单独判断一次
            if cur.elem == item:
                return True
            return False
    3、测试:
    if __name__ == '__main__':
        s = SingeLoopLike()
        s.add(20)
        s.add(10)
        s.append(30)
        s.insert(4, 40)
        s.remove(50)
    
        print(s.is_empty())
        print(s.length())
        s.travel()
        print(s.search(50))
    

    1.3 双向链表【了解】

    • 双向链表特点:每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
      在这里插入图片描述
    # 创建节点类:
    class Node:
        def __init__(self,elem):
            self.elem=elem
            self.next=None # 默认单节点,next为None
            self.pre = None
    
    class DoubleLink():
        def __init__(self):
            self.__head=None
    
        def is_empty(self):
            if self.__head is None:
                return True
            else:
                return False
    
        def length(self):
            cur = self.__head
            count = 0
            while cur != None:
                cur = cur.next
                count += 1
            return count
        # 循环打印链表的值
        def travel(self,):
            if self.is_empty():
                return
            cur = self.__head
            while cur != None:
                print(cur.elem, end=',')
                cur = cur.next
            print()
        # 在头部添加数据
        def add(self,item):
            node = Node(item)
            if not self.is_empty():
                node.next = self.__head
                self.__head.pre = node
            self.__head = node
        # 链表尾部添加元素
        def append(self, item):
            node = Node(item)
            # 如果链表为空
            if self.is_empty():
                self.__head = node
            else:
                cur = self.__head
                # 找到最后一个节点,cur.next == None时cur为最后一个节点。
                while cur.next != None:
                    cur = cur.next
                cur.next = node
                node.pre = cur
        # 指定位置添加元素
        def insert(self, pos, item):
            node = Node(item)
            if pos <= 0:
                self.add(item)
            elif pos > (self.length()-1):
                self.append(item)
            else:
                cur = self.__head
                count = 0
                while count < pos-1:
                    count += 1
                    cur = cur.next
                node.next = cur.next
                cur.next.pre = node
                cur.next = node
                node.pre = cur
    
        # 删除节点
        def remove(self, item):
            cur = self.__head
            while cur.next != None:
                if cur.elem == item:
                    # 判断是否是头部节点
                    if cur == self.__head:
                        self.__head = cur.next
                        cur.next.pre = None
                    else:
                        cur.next.pre = cur.pre
                        cur.pre.next = cur.next
                    return
                else:
                    cur = cur.next
            if cur.elem == item:
                # 判断是否只有一个元素,如果只有一个元素则head指向None
                if cur.pre == None:
                    self.__head = None
                # 如果不是只有一个元素,则判断是最后一个元素
                else:
                    cur.pre.next = None
    
        # 查找节点是否存在
        def search(self, item):
            cur = self.__head
            # if self.is_empty():
            #     return False
            while cur != None:
                if cur.elem == item:
                    return True
                cur = cur.next
            return False
    
    
    if __name__ == '__main__':
        s = DoubleLink()
        print(s.is_empty())
        s.add(10)
        s.add(20)
        s.append(100)
        s.append(500)
        s.insert(0, 300)
        s.remove(10)
        print(s.length())
        s.travel()
        print(s.search(300))
    

    二、链表与顺序表的对比

    • 链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。

    • 链表与顺序表的各种操作复杂度:
      在这里插入图片描述

    • 链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。顺序表查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。

    展开全文
  • 由于学习链表,所以,用C++写了单向链表,单项循环链表,双向链表,并进行了测试。 均为无哨兵链表。欢迎大家测试,若发现错误,还请指出。以便我稍后改进。 链接:...

    由于学习链表,所以,用C++写了单向链表,单项循环链表,双向链表,并进行了测试。

    均为无哨兵链表。欢迎大家测试,若发现错误,还请指出。以便我稍后改进。

    链接: https://github.com/hitskyer/course/tree/master/dataAlgorithm/dongyaxing/SingleCircleLink_file

    展开全文
  • 一、单向链表 1、链表的提出 (1)链表和顺序表的区别??? 顺序表的特点:存储空间必须连续,而且一旦不够的情况下就涉及到动态的改变数据区。 思考:有没有一种数据结构,能够在进行扩充的时候,原有的数据...

    一、单向链表

    1、链表的提出

    (1)链表和顺序表的区别???

    顺序表的特点:存储空间必须连续,而且一旦不够的情况下就涉及到动态的改变数据区。

    思考:有没有一种数据结构,能够在进行扩充的时候,原有的数据完全不用变,你多一个,我就增加一个。====>链表

    c4b2d78c79621f1ff1b9c5593ad3084d9ce.jpg【简单的指向】===>链表的操作:7e0a7ea4c70ba35de00f6ede58584d4e0cb.jpg

    【所以:链表的实现方式,把数据分成两部分:数据区+链接区

    (2)链表和顺序表统称为:线性表

    • 顺序表:将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示。

    • 链表:将元素存放在通过链表构造起来的一系列存储块中。

    2、单链表的ADT模型

    单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。

    SouthEast

    • 表元素域elem用来存放具体的数据。
    • 链接域next用来存放下一个节点的位置(python中的标识)
    • 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

    3、单链表与顺序表的对比

    链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。

    链表与顺序表的各种操作复杂度如下所示:

    操作链表顺序表
    访问元素o(n)o(1)
    在头部插入/删除o(1)o(n)
    在尾部插入/删除o(n)o(1)
    在中间插入/删除o(n)o(n)

    注:

            虽然表面看起来复杂度都是 O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作

            链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)

            顺序表查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。

    分析:

    (1)原有顺序表访问元素,在尾部插入/删除的时间复杂度都是O(1),但是换成链表时,时间复杂度是O(n),为什么还要用链表呢?

    答:假设要存储一个巨大的数据,而操作系统没有一块连续的内存给你分配,这时候可以使用链表。

    因为链表可以把整个内存中所有分散的、只要可用的,通过链表进行串起来,但是顺序表达不到这样的效果。

    (2)顺序表的优点:存取元素时,可以通过O(1)的方式一次性定位。

    缺点:顺序表的空间必须是连续的,如果一旦动态的改变,整个存储区都得改变。而且若是存储大数据时,没有相应的存储空间,则达不到要求。

    (3)链表的特点:对于分散的、离散的内存空间可以达到充分的利用。但是利用的同时,额外的开销也是大的。且利用链表存取元素时的时间复杂度是O(n)。

    重点:(4)在中间插入/删除,链表和顺序表的时间复杂度都是O(n),但是其中的n所代表的重复的操作是不一样的

                                对于链表来说,n花费在遍历上;对于顺序表,n花费在数据搬迁上。

    4、单链表:节点的实现+单链表中的操作

    【操作:is_empty()链表是否为空;length()链表长度;travel()遍历整个链表;add(item)链表头部添加元素;append(item)链表尾部添加元素;insert(pos,item)指定位置添加元素;remove(item)删除节点;search(item)查找节点】

    代码如下:

    class Node(object):  #链表中的节点
        def __init__(self,elem):
            self.elem=elem  #元素区
            self.next=None  #刚创建的节点,默认是在链表之外,所以它的指向是Null
    
    class SingleLinkList(object):  #单向链表
    
        def __init__(self,node=None):  #定义的节点默认是None
            self.__head=node  #初始化的头结点   指向   定义的node节点
    
        def is_empty(self):
            '''链表是否为空'''
            return self.__head==None  #链表的头节点指向None,则返回True,为空;否则不为空!
    
        def length(self):
            '''链表长度'''
            cur = self.__head  # cur游标,用来移动遍历节点
            count = 0  # 记录数量
            while cur != None:
                count += 1
                cur = cur.next  # 每次往后移一个位置
            return count
    
        def travel(self):
            '''遍历整个链表'''
            cur=self.__head  #cur游标,用来移动遍历节点
            while cur!=None:
                print(cur.elem,end=' ')
                cur=cur.next  #每次往后移一个位置
            print("")  #相当于多次调用travel时换行
    
        def add(self,item):
            '''链表头部添加元素'''
            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):
            '''指定位置添加元素  pos 从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):
                    pre=pre.next
                    count+=1
                #跳出while循环时,count=pos-1,此时pre指向pos-1位置,在插入节点位置的前一个
                node.next=pre.next
                pre.next=node
    
        def remove(self,item):
            '''删除节点'''
            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  #先移动pre游标
                    cur=cur.next  #再移动cur游标
    
        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__':
        l1=SingleLinkList()
        print(l1.is_empty())  #True
        print(l1.length())  #0
        l1.append(1)
        print(l1.is_empty())  #False
        print(l1.length())  #1
        l1.append(2)
        l1.append(3)
        l1.append(4)
        l1.append(5)
        l1.add(8)
        l1.travel()  # 8 1 2 3 4 5
        l1.insert(-1,9)
        l1.travel()  #9 8 1 2 3 4 5
        l1.insert(2,100)
        l1.travel()  #9 8 100 1 2 3 4 5
        l1.insert(10,200)
        l1.travel()  #9 8 100 1 2 3 4 5 200
        l1.remove(100)
        l1.travel()  #9 8 1 2 3 4 5 200
        l1.remove(9)
        l1.travel()  #8 1 2 3 4 5 200
        l1.remove(200)
        l1.travel()  #8 1 2 3 4 5

    二、单向循环链表

    单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。c96029daf11e852e6cfce0bba95c4e9191e.jpg

    单向循环链表:节点的实现+单链表中的操作

    【单向循环链表的操作:is_empty()链表是否为空;length()链表长度;travel()遍历整个链表;add(item)链表头部添加元素;append(item)链表尾部添加元素;insert(pos,item)指定位置添加元素;remove(item)删除节点;search(item)查找节点】

    class Node(object):  #节点的构造
        def __init__(self,elem):
            self.elem=elem
            self.next=None
    
    class SingleCycleLinkList(object):  #单向循环链表
    
        def __init__(self,node=None):  #定义的节点默认是None     #【与单项链表不同】
            self.__head=node  #初始化的头结点   指向   定义的node节点
            if node:  #如果传入不为None
                node.next=node #设置循环
    
        def is_empty(self):
            '''链表是否为空'''
            return self.__head==None  #链表的头节点指向None,怎返回True,为空;否则不为空!
    
        def length(self):          #【与单项链表不同】
            '''链表长度'''
            if self.is_empty():  #如果链表时空链表,返回0
                return 0
            #链表不为空
            cur = self.__head  # cur游标,用来移动遍历节点
            count = 1  # 记录数量
            while cur.next!=self.__head:
                count += 1
                cur = cur.next  # 每次往后移一个位置
            return count
    
        def travel(self):
            '''遍历整个链表'''
            cur=self.__head  #cur游标,用来移动遍历节点
            while cur.next!=self.__head:
                print(cur.elem,end=' ')
                cur=cur.next  #每次往后移一个位置
            print("")  #相当于多次调用travel时换行
    
        def add(self,item):    #【与单项链表不同】  (需要找到尾节点,然后尾节点指向头结点)   【先找到尾节点,然后插入头结点,最后尾节点指向头结点】
            '''链表头部添加元素'''
            node=Node(item)
    
            if self.is_empty():  #若是空链表
                self.__head=node
                node.next=node
            else:  #不是空链表
                cur=self.__head
                while cur.next!=self.__head:
                    cur=cur.next
                #退出循环时,cur指向尾节点
                node.next=self.__head
                self.__head=node
                cur.next=self.__head
    
        def append(self,item):  #【与单项链表不同】
            '''链表尾部添加元素'''
            node=Node(item)  #将要添加的元素转化为节点
            if self.is_empty():  #如果链表为空
                self.__head=node
                node.next=node
            else:
                cur=self.__head
                while cur.next!=self.__head:
                    cur=cur.next
                node.next=self.__head
                cur.next=node
    
        def insert(self,pos,item):   #【与单项链表相同,不修改】
            '''指定位置添加元素  pos 从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):
                    pre=pre.next
                    count+=1
                #跳出while循环时,count=pos-1,此时pre指向pos-1位置,在插入节点位置的前一个
                node.next=pre.next
                pre.next=node
    
        def remove(self,item):  #【与单项链表相同,小修改】
            '''删除节点'''
            cur=self.__head
            pre=None
            while cur.next!=self.__head:
                if cur.elem==item:  #找到这个节点
                    #先判断此节点是否是头结点
                    if cur==self.__head: #头结点,然后找尾节点
                        rear=self.__head
                        while rear.next!=self.__head:
                            rear=rear.next
                        self.__head=cur.next
                        rear.next=self.__head
                    else: #中间节点
                        pre.next=cur.next
                    return ''
                else:
                    pre=cur  #先移动pre游标
                    cur=cur.next  #再移动cur游标
            #退出循环,cur指向尾节点
            if cur.elem==item:
                if cur==self.__head: #链表只有一个节点
                    self.__head=Node
                else:
                    pre.next=cur.next
    
        def search(self,item):  #【与单项链表大致相同,小修改】
            '''查找节点是否存在'''
            if self.is_empty():  #如果是空链表,就直接返回 False
                return False
            cur=self.__head
            while cur.next!=self.__head:
                if cur.elem==item:
                    return True
                else:
                    cur=cur.next
            #退出循环时,cur指向尾节点   【需要判断尾节点是否指向item】
            if cur.elem==item:
                return True
            return False
    
    if __name__ == '__main__':
        l1=SingleCycleLinkList()
        print(l1.is_empty())  #0
        print(l1.length())  #True
    
        l1.append(1)
        print(l1.is_empty())  #False
        print(l1.length())  #1
        l1.append(2)
        l1.append(3)
        l1.append(4)
        l1.append(5)
        l1.add(8)
        l1.travel()  # 8 1 2 3 4 5
        l1.insert(-1,9)
        l1.travel()  #9 8 1 2 3 4 5
        l1.insert(2,100)
        l1.travel()  #9 8 100 1 2 3 4 5
        l1.insert(10,200)
        l1.travel()  #9 8 100 1 2 3 4 5 200
        l1.remove(100)
        l1.travel()  #9 8 1 2 3 4 5 200
        l1.remove(9)
        l1.travel()  #8 1 2 3 4 5 200
        l1.remove(200)
        l1.travel()  #8 1 2 3 4 5

    三、双向链表

    每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;

                                    而另一个指向下一个节点,当此节点为最后一个节点是,指向空值。

    1719787a3454977e5e9136ffc864970e41b.jpg

    双向链表:节点的实现+单链表中的操作

    【单向循环链表的操作:is_empty()链表是否为空;length()链表长度;travel()遍历整个链表;add(item)链表头部添加元素;append(item)链表尾部添加元素;insert(pos,item)指定位置添加元素;remove(item)删除节点;search(item)查找节点】

    class Node(object):  #节点
        def __init__(self,elem):
            self.elem=elem  #元素区
            self.next=None  #刚创建的节点,默认是在链表之外,所以它的后继节点为Null
            self.prev=None  #刚创建的节点,默认是在链表之外,所以它的前驱节点为Null
    
    class DoubleLinkList(object):  #双向链表
    
        def __init__(self,node=None):  #定义的节点默认是None    【与单链表相同】
            self.__head=node  #初始化的头结点   指向   定义的node节点
    
        def is_empty(self):  #【与单链表相同】
            '''链表是否为空'''
            return self.__head==None  #链表的头节点指向None,则返回True,为空;否则不为空!
    
        def length(self):  #【与单链表相同】
            '''链表长度'''
            cur = self.__head  # cur游标,用来移动遍历节点
            count = 0  # 记录数量
            while cur != None:
                count += 1
                cur = cur.next  # 每次往后移一个位置
            return count
    
        def travel(self):  #【与单链表相同】
            '''遍历整个链表'''
            cur=self.__head  #cur游标,用来移动遍历节点
            while cur!=None:
                print(cur.elem,end=' ')
                cur=cur.next  #每次往后移一个位置
            print("")  #相当于多次调用travel时换行
    
        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):  #【与单链表不同】
            '''指定位置添加元素  pos 从0开始'''
            if pos<=0:  #为头插法
                self.add(item)
            elif pos>self.length()-1:  #尾插法
                self.append(item)
            else:
                cur=self.__head
                node=Node(item)
                count=0
                while count<(pos-1):
                    cur=cur.next
                    count+=1
                #跳出while循环时,cur指向pos位置
                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.elem==item:  #找到这个节点
                    #先判断此节点是否是头结点
                    if cur==self.__head: #头结点
                        self.__head=cur.next
                        if cur.next:  #判断链表是否只有一个节点
                            cur.next.prev=None
                    else: #不是头结点
                        cur.prev.next=cur.next
                        if cur.next:
                            cur.next.prev=cur.prev
                    break
                else:
                    cur=cur.next  #移动cur游标
    
        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__':
        l1=DoubleLinkList()
        print(l1.is_empty())  #True
        print(l1.length())  #0
        l1.append(1)
        print(l1.is_empty())  #False
        print(l1.length())  #1
        l1.append(2)
        l1.append(3)
        l1.append(4)
        l1.append(5)
        l1.add(8)
        l1.travel()  # 8 1 2 3 4 5
        l1.insert(-1,9)
        l1.travel()  #9 8 1 2 3 4 5
        l1.insert(2,100)
        l1.travel()  #9 8 100 1 2 3 4 5
        l1.insert(10,200)
        l1.travel()  #9 8 100 1 2 3 4 5 200
        l1.remove(100)
        l1.travel()  #9 8 1 2 3 4 5 200
        l1.remove(9)
        l1.travel()  #8 1 2 3 4 5 200
        l1.remove(200)
        l1.travel()  #8 1 2 3 4 5

    注:

        双向链表DoubleLinkList()中,可以使用继承,因为其部分操作(is_empty(),length(),travel(),search(item))与单链表SingleLinkList()中相应的操作相同。

    转载于:https://my.oschina.net/pansy0425/blog/3070785

    展开全文
  • 单向循环链表 –多个节点只有一个节点的结构分析 双向循环链表: 双向循环链表 –多个节点只有一个节点的结构分析 双向循环链表直接体现为 双向循环,一般的单链表只有节点数据datanext指向地址(应该也是...
  • 链式存储结构是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。又称链表链表特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的...
  • 显然,循环链表和普通链表的区别在于,尾节点的next指针指向了头节点。而对于这条指向的维护也只在于add和remove方法,因此循环链表仅仅在这个方法上有所不同。(普通链表的创建可见链表(一)用Java语言实现单向...
  • 3、单向链表 结构图:  分为两部分:数据+下一个节点的引用 代码实现: /** * 单链表 */ public class SingleNode { private int data; private SingleNode next; public SingleNode(int data)...
  • C语言之链表:单向链表循环链表,双向链表 提起链式存储结构,其与数组是两个非常基础的数据结构,每当提到链式存储结构时,一般情况下我们都会将其与数组放到一块儿来比较。 对于数组与链表,从结构上来看,数组...
  • 1 单向循环链表 单向循环链表,它的最后一个结点指向头结点,形成一个环。在节点结构上单链表是一样的。 从单向循环链表中的任何一个结点出发都能找到任何其他结点。 1.1 节点代码 class LoopNode(var value: Int)...
  • 每日一句 It’s gonna be ok. 一切都会好的。 内容概要 单向循环链表 首先来看看图示: 图展示的是一个单向循环链表,他跟以上的单向链表对比只是...linklist init_list(void) // 带有头结点的单循环链表 { linklis
  • 单向循环链表

    2019-01-14 10:53:12
    单向循环链表 单向循环链表: 在单向链表中,头指针是相当重要的,因为单向链表的操作都需要头指针,所以如果头指针丢失或者破坏, 那么整个链表都会遗失,并且浪费链表内存空间... '''单循环链表的结点:next默认...
  • 双向链表节点模板的创建''' class Node(object): def __init__(self,item): self.item = item '''单个节点的后继指针初始值设为None''' self.next = None &#...
  • 双向链表 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。 操作 is_...
  • 一个单向链表中可能存在循环,如何判断单向链表中是否存在循环,又如何找到循环部分的起始节点?如果是非循环链表,如何找到中间节点? 本文结合网上找到的资料及自己的分析,进行了总结。
  • 单向循环链表 单向循环聊表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。单链表相比,循环单链表的长处使从链尾到链头...
  • 单向循环链表 双链表 双链表又称为双向链表/双面链表,每个节点有两个链接,一个指向前一个节点,当前节点为第一个节点时,指向控制;一个指向下一个节点,当前节点为后一个节点时,当此节点为最后一个节点时,...
  • 既然大家都是链表,那么双向链表和单向循环链表单向链表不就是爸爸和儿子的关系嘛!那么我们就可以使用继承来实现双向链表和单向循环链表了,使得其中的很多代码都可以重用,提高了代码编写的效率。 ...
  • 所以,这几天我也写了单向循环链表和双向循环链表。 感觉区别不太大⊙0⊙。明天就要开始看栈和队列了。听说数据结构越学越难。希望我不会晕倒吧。 (>_<分享代码啦,感觉自己的代码风格好丑。最...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,630
精华内容 7,452
关键字:

单向链表和单循环链表