`
lanqiu17
  • 浏览: 17716 次
社区版块
存档分类
最新评论

双链表

阅读更多

上次单链表中有个问题,就是remove 方法有误,在这里已经修正了,下面是双链表的实现。其实,双链表已比较简单,就是在存储节点中加上一个指向上个节点的引用(呵呵,这好像是java的术语) 具体代码如下:

# -*- coding: cp936 -*-
#---------------------------------------------
#                                             
#author  chile                                  
#version  1.0                                
#since                                       
#date                                         
#desc  双链表                                 
#                                             
#                                             
#                                             
#---------------------------------------------
class DoubleLinkList:
    def __init__(self):
        self.root = DoubleLinkList.Entry()
        self.entry = self.root
        self.list = list()
        self.tally = 0
    
    #新增的数据都是插入在尾部
    def add(self,value):
        temp = self.Entry(pre = self.entry,value = value)
        self.entry.next = temp 
        self.entry = temp
        self.tally += 1
    
    #在头部添加
    def addFirst(self,value):
        entry = self.root.next  
        temp = self.Entry(pre = self.root , next = entry,value = value)
        self.root.next = temp  
        self.tally += 1
        
    def get(self,index):
        if index > self.tally or index < 0:
            return  #其实应该抛出异常
        mid = self.tally / 2
        e = self.root.next
        if index < mid:
            for i in range(index):
                e = e.next  
        else:
            for i in range(self.tally):
                if (i == index):
                    break
                e = e.next  
        return e.value
    
    def getLast(self):
        return self.entry.value
    
    def getFirst(self):
        return self.root.next.value
    
    def remove(self,value):
        e = self.root.next
        self.removeEntry(self.root,e, value)
        if self.isRemove:
            self.tally -= 1
                
    def removeEntry(self,pre,current,value):
        self.isRemove = False
        if current == None:
            self.isRemove = False
            return
        if current.value == value:
            pre.next = current.next
            self.isRemove = True
        else:
            self.removeEntry(current,current.next, value)    
            
    def removeFirst(self):
        root = self.root
        entry = root.next;
        root.next = entry.next
        entry.next.pre = root
        self.tally -= 1
    
    def size(self):
        return self.tally
    
    def all(self):
        self.list = list()
        self.iterator(self.root.next)
        return self.list
    
    def iterator(self,entry):
        if entry != None:
            self.list.append(entry.value)
            self.iterator(entry.next)
            
    #内部类 用于存放节点的值,以及下个点的引用
    class Entry:
        
        def __init__(self, pre = None , next = None , value = None):
            self.next = next #下一个节点
            self.pre = pre   #上一个节点
            self.value = value #节点存储的值
            
            

link = DoubleLinkList()
link.add(1)
link.add(2)
link.addFirst(3)
link.add(5)
link.add(4)
link.add(7)
link.remove(5)
print link.all(), link.size()
link.addFirst(5)
print link.all(), link.size()
link.removeFirst()
print link.all(), link.size()
print link.getFirst() , link.getLast() , link.get(3)

    水平有限哈,写的比较简单。如果有什么问题,请指正。希望和有兴趣的共同交流。

2
2
分享到:
评论

相关推荐

    数据结构的双链表算法

    双链表是数据结构中的一种重要类型,它在计算机科学中有着广泛的应用。与单链表相比,双链表的特点在于每个节点不仅包含指向下一个节点的指针,还包含一个指向前一个节点的指针,这使得双向操作更加便捷。 在双链表...

    支持类模版的C++双向链表

    在C++编程中,双向链表是一种非常重要的数据结构,它允许在列表的任一位置进行插入和删除操作,而不必像数组那样依赖于索引。在这个“支持类模版的C++双向链表”中,我们将探讨如何利用C++的模板特性来实现一个灵活...

    双向链表双向链表双向链表

    双向链表是一种高级数据结构,它在计算机科学中被广泛应用于各种算法和程序设计中。与单链表相比,双向链表的主要特点是每个节点不仅包含指向下一个节点的指针,还包含一个指向前一个节点的指针。这种设计使得双向...

    java 单链表和双向链表的实现

    本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现,以及相关的操作,如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先,我们来理解单链表和双向链表的基本概念。单链表是一种线性...

    C++双向链表统计文章单词出现频率

    在这个特定的项目中,“C++双向链表统计文章单词出现频率”是一个涉及数据结构和算法的应用,目标是实现一个程序来分析文本文件,计算并显示文章中每个单词出现的次数。双向链表作为数据结构的核心,其特点是每个...

    Linux内核双向链表简单分析

    其中,双向链表(双链表)不仅支持向后指针,还支持向前指针,这使得双向链表在操作上更为灵活,特别是在需要频繁进行反向遍历的情况下。 #### list链表组织结构 在Linux内核中,双向链表的实现主要依赖于`struct ...

    用双向链表做的n的阶乘

    在编程领域,双向链表是一种数据结构,它允许在列表中的元素之间进行前向和后向的导航。这种数据结构在处理需要频繁插入、删除或遍历操作的问题时特别有用。而“n的阶乘”是数学概念,表示1到n的所有整数的乘积,记...

    双向链表的操作

    双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成...

    创建双向链表_双向链表_

    双向链表是一种特殊类型的数据结构,与常见的单向链表相比,它具有更丰富的操作能力,可以支持前后两个方向的遍历。本篇文章将深入探讨如何创建双向链表以及其在增加和删除操作中的应用。 双向链表的每个节点不仅...

    操作系统课设-线程安全的双向链表

    操作系统课程设计中实现线程安全的双向链表是一项重要的实践任务,这涉及到多线程编程、数据结构以及并发控制等核心知识点。在这个项目中,我们主要关注如何在多线程环境下构建一个能够正确操作(如插入、删除)而不...

    双向链表的增删改查

    在计算机科学中,数据结构是组织和管理数据的重要方式,而链表作为一种基本的数据结构,被广泛用于各种算法和程序设计中。双向链表(Double Linked List)是链表的一种变体,它允许我们在列表中的每个节点处进行前向...

    数据结构-双向链表

    双向链表是一种特殊的数据结构,它在编程中具有重要的应用。本文将深入探讨双向链表的概念,实现,以及如何进行基本操作。 双向链表,顾名思义,是一种链式存储结构,其中每个节点包含两个指针,一个指向前一个节点...

    双向链表模板类简单实现

    在编程领域,数据结构是构建复杂算法的基础,而链表作为一种基本的数据结构,常常被用于解决各种问题。本文将深入探讨双向链表及其在C++中的模板类实现,以"双向链表模板类简单实现"为主题,我们来详细了解一下这个...

    单链表、双链表、循环链表的操作

    链表可以分为单链表、双链表和循环链表三种,下面我们将详细介绍这些链表的操作。 单链表 单链表是一种基本的链表结构,其中每个节点只有一个指针指向下一个节点。单链表的实现可以通过结构体来实现,如上面的代码...

    数据结构源代码之双向链表

    ### 数据结构源代码之双向链表 #### 概述 本文档主要介绍如何通过C语言实现双向链表的基本操作。继单链表之后,双向链表作为一种更灵活的数据结构,支持从前向后以及从后向前的遍历。双向链表在每个节点中除了包含...

    数据结构 双向链表(C++)

    双向链表是一种特殊的数据结构,它在计算机程序设计中扮演着重要角色,特别是在C++这样的编程语言中。本节将深入探讨双向链表的概念、其结构、操作以及C++中的实现。 双向链表与单链表不同,它允许每个节点不仅有一...

    双链表的学习

    双向链表是一种数据结构,它在单链表的基础上增加了向前和向后指针,使得节点不仅可以访问其后继节点,还可以访问其前驱节点。这种数据结构在计算机科学中有着广泛的应用,特别是在需要高效地进行插入、删除操作的...

    stm32f103 双向链表

    在这个项目中,我们讨论的是如何在STM32F103上实现一个双向链表的数据结构。双向链表是一种特殊的数据结构,它允许我们在列表中的节点之间进行前向和后向的移动,这在处理动态数据集合时非常有用。 首先,我们要...

    大数阶乘 双向链表

    本主题聚焦于如何使用双向链表这一数据结构来实现大数阶乘的计算。双向链表允许我们有效地存储和操作大数,同时保持良好的性能。 首先,我们需要了解双向链表的基本概念。双向链表是一种线性数据结构,其中每个节点...

    C语言编写的双向链表

    在编程领域,数据结构是构建复杂算法的基础,而链表作为一种基本的数据结构,常常被用于实现动态内存管理、高效搜索和排序等操作。双向链表是链表的一种变体,它在每个节点中不仅存储了数据,还包含了指向前后节点的...

Global site tag (gtag.js) - Google Analytics