专栏首页机器学习和数学[数据结构与算法] 链表的其他类型

[数据结构与算法] 链表的其他类型

单链表是最简单的链表,单链表的一种变形就是循环单链表,其中最后一个结点的next域不用None,而是指向表的第一个结点,这样就形成了一种循环结构,所以叫循环单链表。

双链表:单链表只有1个方向的链接,只能做一个方向的扫描和逐步操作。单链表的next指针域指向下一个结点,而双链表结点除了具有next指针外,还有一个previous指针,指向上一个结点。单链表中查找元素只能从头结点开始,根据他的next指针域找到下一个结点,而双链表最大的区别在于不仅能找到下一个结点,还能找到上一个结点。

循环双链表:然后看下什么是循环双链表,循环单链表是把最后一个结点的next指针域指向了首结点,而循环双链表除了这个以外,还有首结点的previous指针域指向尾结点。这就是循环双链表。

下面用Python实现循环单链表和双链表。

Github : https://github.com/Alvin2580du/Data-Structures-and-Algorithms.git

# - * - coding:utf-8 - * -
"""定义节点类"""


class LNode:
    def __init__(self, x, next_=None):
        self.elem = x
        self.next = next_


"""
定义单链表类
"""


class LList:
    def __init__(self):
        self._head = None

    def length(self):
        count = 0  # 数目
        # 当前节点
        current = self._head
        while current != None:
            count += 1
            # 当前节点往后移
            current = current.next
        return count

    def is_empty(self):
        return self._head is None

    def prepend(self, elem):
        self._head = LNode(elem, self._head)

    """在链表头部添加元素"""

    def add(self, elem):
        node = LNode(elem)
        # 结点的next指针域指向头结点
        node.next = self._head
        # 头结点称为新的结点
        self._head = node

    def pop(self):
        if self._head is None:
            raise ValueError("in pop")
        e = self._head.elem
        self._head = self._head.next
        print("head is :%s" % self._head)
        return e

    # 后端操作
    def append(self, elem):
        # 当链表为空时
        if self._head is None:
            self._head = LNode(elem)
            return
        current = self._head
        while current.next is not None:
            current = current.next

        current.next = LNode(elem)

    def pop_last(self):
        if self._head is None:
            raise ValueError("in pop_last")
        p = self._head
        if p.next is None:
            e = p.elem
            self._head = None
            return e
        while p.next.next is not None:
            p = p.next
        e = p.next.elem
        p.next = None
        return e

    def find(self, pred):
        p = self._head
        while p is not None:
            if pred(p.elem):
                return p.elem
            p = p.next

    def printall(self):
        p = self._head
        while p is not None:
            if p.next is not None:
                print(', ')
            p = p.next


"""
定义循环单链表类
"""


class LCList:
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head is None

    # 求链表长度
    def length(self):
        if self.is_empty():
            return 0
        count = 1  # 数目
        # 当前节点
        current = self._head
        # 当前节点的下一个节点不是头结点则继续增加
        while current.next != self._head:
            count += 1
            # 当前节点往后移
            current = current.next
        return count

    # add(elem) 链表头部添加元素
    def add(self, elem):
        node = LNode(elem)
        if self.is_empty():
            # 空链表
            self.__head = node
            node.next = node
        else:
            # 非空链表添加
            current = self.__head
            # 查找最后一个节点
            while current.next != self.__head:
                current = current.next
            # 新节点的下一个节点为旧链表的头结点
            node.next = self.__head
            # 新链表的头结点为新节点
            self.__head = node
            # 最后节点的下一个节点指向新节点
            current.next = node

    def prepend(self, elem):
        p = LNode(elem)
        # 如果为空
        if self._head is None:
            p.next = p
            self._head = p
        else:
            p.next = self._head.next
            self._head.next = p

    def append(self, elem):
        self.prepend(elem)
        self._head = self._head.next

    def pop(self):
        if self._head is None:
            raise ValueError("in pop of CLList")
        p = self._head.next
        if self._head is p:
            self._head = None
        else:
            self._head.next = p.next
        return p.elem

    # search(elem) 查找节点是否存在
    def search(self, elem):
        # 当前节点
        if self.is_empty():
            # 空链表直接返回False
            return False
        current = self.__head
        while current.next != self.__head:
            if current.elem == elem:
                # 找到了
                return True
            else:
                current = current.next
        # 判断最后一个元素
        if current.elem == elem:
            return True
        return False

    def printall(self):
        if self.is_empty():
            return
        p = self._head.next
        while True:
            print (p.elem)
            if p is self._head:
                break
            p = p.next


"""定义双链表结点类,在LNode的基础上派生类"""


class DLNode(LNode):
    def __init__(self, elem, prev=None, next_=None):
        LNode.__init__(self, elem, next_)
        self.prev = prev


"""
定义双链表类
"""


class Double_LList(LList):
    def __init__(self):
        LList.__init__(self)

    def is_empty(self):
        return self._head is None
        # length() 链表长度

    def length(self):
        count = 0  # 数目
        # 当前节点
        current = self._head
        while current != None:
            count += 1
            # 当前节点往后移
            current = current.next
        return count

    # add(elem) 链表头部添加元素
    def add(self, elem):
        node = DLNode(elem)
        # 新节点的下一个节点为旧链表的头结点
        node.next = self.__head
        # 新链表的头结点为新节点
        self.__head = node
        # 下一个节点的上一个节点指向新增的节点
        # 相当于是第一个结点指向新添加结点
        node.next.prev = node

    def prepend(self, elem):
        p = DLNode(elem, None, self._head)
        if self._head is None:
            self._head = p
        else:
            p.prev.prev = p
        self._head = p

    def append(self, elem):
        p = DLNode(elem, self._head, None)
        if self._head is None:
            self._head = p
        else:
            p.prev.next = p
        self._head = p

    def pop(self):
        if self._head is None:
            raise ValueError("in pop_last of DDList")
        e = self._head.elem
        self._head = self._head.next
        if self._head is not None:
            self._head.prev = None
        return e

    def pop_last(self):
        if self._head is None:
            raise ValueError("in pop_last of DLList")

        e = self._head.elem
        self._head = self._head.prev
        if self._head is None:
            self._head = None
        else:
            self._head.next = None
        return e

本文分享自微信公众号 - 机器学习和数学(ML_And_Maths),作者:Alvin_2580

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-09-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [数据结构与算法] 链接表总结

    上一次说到了顺序表,链接表和顺序表一样,也是线性表。那为什么有了线性表还要有链接表呢?总之就是当数据过大时,顺序表存在一些存储方面的限制,而链接表比顺序表要更有...

    用户1622570
  • [数据结构与算法] 线性表总结

    线性表也是基本的数据结构之一,Python里面的list和tuple,就是线性表的一种实现。 首先什么是表呢,其实很简单,比如【元素1,元素2,。。。,元素n】...

    用户1622570
  • [编程经验]Python中的Lambda,Map, Reduce小结

    今天要和大家分享的是Python匿名函数(anonymous functions),也叫lambda函数。匿名函数的意思就是说这个函数没有显式的函数名,因为一般...

    用户1622570
  • LEETCODE - Linked List 题目思路汇总

    浏览了一下 Leetcode 上 Linked List 的题目,我把它分为 6 类: 调换顺序 删除 合并 环 变身 复制 做Leetcode还是要归类总结才...

    杨熹
  • PyQt 的动作组(QActionGroup)

    动作组(QActionGroup),是用于管理多个可选型动作(checkable QAction)的类,它可以保证组中所有的动作只要有一个“开”,则其他的所有动...

    用户6021899
  • 使用 python 进行微信好友分析

    【特别提醒】:pyecharts 库用的是0.5.x版本,而在 pip 中安装的为1.x.x版本,因此需要自行到【官网】中下载。

    用户2398817
  • python 实现线性链表(单链表)

    初学python,拿数据结构中的线性链表存储结构练练手,理论比较简单,直接上代码。

    用户2398817
  • 数据结构-栈的定义及python实现

    class Node(object): def __init__(self,value): self.value=value ...

    致Great
  • 【leetcode 简单】 第六十七题

    用户2398817
  • python pyqt5 信号连接、断开、发射

    from PyQt5.QtCore import QObject , pyqtSignal

    用户5760343

扫码关注云+社区

领取腾讯云代金券