Python 实现单向链表

单向链表

#!usr/bin/env python  
# -*- coding:utf-8 -*-

""" 
@author:yzk13 
@time: 2018/04/15
单向链表
"""


class Node(object):
    """
    节点类
    """

    def __init__(self, value, next):
        self.value = value
        # 下一个节点
        self.next = next

class LinkedList(object):
    """
    链表
    """

    def __init__(self):
        self.root = None

    def addNode(self, value):
        """
        添加Node
        :return:
        """
        if self.root == None:
            self.root = Node(value=value, next=None)
            return self.root
        else:
            # 有头节点,需要遍历到链表尾部,然后添加节点
            cursor = self.root
            while cursor.next != None:
                cursor = cursor.next
            cursor.next = Node(value=value, next=None)
            return self.root

    def append(self, value):
        """
        在尾部添加Node
        :return:
        """
        self.addNode(value)

    def prepend(self, value):
        """
        在表头添加Node
        :param value:
        :return:
        """
        if self.root == None:
            self.addNode(value)
        else:
            newNode = Node(value, self.root)
            self.root = newNode

    @property
    def length(self):
        """
        获取链表长度
        :return:
        """
        counter = 0
        if self.root == None:
            counter = 0
            return counter
        else:
            cursor = self.root
            while cursor != None:
                counter += 1
                cursor = cursor.next
            return counter

    def insert(self, index, value):
        """
        在index处插入Node
        :param index:
        :param value:
        :return:
        """
        if self.root == None:
            return None
        if index < 0 or index > self.length - 1:
            print('Index 非法,超出索引')
        elif index == 0:
            # 表头
            self.prepend(value)
        elif index == self.length - 1:
            # 表尾
            self.append(value)
        else:
            # 使用计数器来确定位置
            counter = 1
            pre = self.root
            cursor = self.root.next
            while cursor != None:
                if counter == index:
                    tmp = Node(value, Node)
                    pre.next = tmp
                    tmp.next = cursor
                    break
                else:
                    counter += 1
                    pre = cursor
                    cursor = cursor.next

    def delNode(self, index):
        """
        删除Node
        :param index:
        :return:
        """
        if self.root == Node:
            return None
        if index < 0 or index > self.length - 1:
            print('Index 非法,超出索引')
        elif index == 0:
            self.root = self.root.next
        else:
            pre = self.root
            cursor = pre.next
            counter = 1
            while cursor != None:
                if index == counter:
                    pre.next = cursor.next
                    break
                else:
                    pre = cursor
                    cursor = cursor.next
                    counter += 1

    def print(self):
        """
        打印链表
        :return:
        """
        if self.root == None:
            print('Nothing')
            return None
        else:
            cursor = self.root
            # 开头的[
            print('[', end='')
            while cursor != None:
                # 输出结尾的]
                if cursor.next == None:
                    print(cursor.value, end=']')
                    cursor = None
                else:
                    print(cursor.value, end=', ')
                    cursor = cursor.next
            print()

    def delValue(self, value):
        """
        删除值为value的Node
        :param value:
        :return:
        """
        if self.root == None:
            return None
        if self.root.value == value:
            self.root = self.root.next
        else:
            pre = self.root
            cursor = pre.next
            while cursor != None:
                if cursor.value == value:
                    pre.next = cursor.next
                    cursor = cursor.next
                    continue
                else:
                    pre = cursor
                    cursor = cursor.next

    def is_empty(self):
        """
        判断链表是否为空
        :return:
        """
        if self.root == None or self.length == 0:
            return True
        else:
            return False

    def getValue(self, index):
        """
        获取指定位置的节点值
        :param index:
        :return:
        """
        if self.root == None:
            return None
        if index < 0 or index > self.length - 1:
            print('Index 非法,超出索引')
        elif index == 0:
            return self.root.value
        else:
            counter = 0
            cursor = self.root
            while cursor != None:
                if counter == index:
                    return cursor.value
                else:
                    counter += 1
                    cursor = cursor.next

    def getValueIndex(self, value):
        """
        获取值为某个值的索引
        :return:
        """
        indexs = []
        if self.root == None:
            return None
        if self.root.value == value:
            self.root = self.root.next
            indexs.append(0)
        else:
            index = 1
            cursor = self.root
            while cursor != None:
                if cursor.value == value:
                    indexs.append(index)
                    index += 1
                cursor = cursor.next
        return indexs

    def peek(self):
        """
        获取尾部节点,且不删除该节点
        :return:
        """
        return self.getValue(self.length - 1)

    def pop(self):
        """
        获取表尾节点并删除
        :return:
        """
        if self.root == None or self.length == 0:
            print('空表')
            return None
        if self.length == 1:
            top = self.root.value
            self.root = None
            return top
        else:
            pre = self.root
            cursor = pre.next
            while cursor.next != None:
                pre = cursor
                cursor = cursor.next
            top = cursor.value
            cursor = None
            pre.next = None
            return top

    def updateNode(self, index, value):
        """
        修改指定位置的节点
        :param index:
        :return:
        """
        if self.root == None:
            return None
        if index < 0 or index > self.length - 1:
            print('Index 非法, 索引不在范围内')
        if index == 0:
            self.root.value = value
        else:
            cursor = self.root.next
            counter = 1
            while cursor != None:
                if counter == index:
                    cursor.value = value
                    break
                cursor = cursor.next
                counter += 1

    def delDuplecate(self):
        """
        删除重复的元素  ????????????
        :return:
        """
        # 使用一个map来存放即可,类似于变形的“桶排序”
        if self.root == None:
            return None
        if self.length == 1:
            return None
        pre = self.root
        cursor = pre.next
        dic = {}
        # 为字典赋值
        temp = self.root
        while temp != None:
            dic[str(temp.value)] = 0
            temp = temp.next
        temp = None
        # 开始实施删除重复元素的操作
        while cursor != None:
            if dic[str(cursor.value)] == 1:
                pre.next = cursor.next
                cursor = cursor.next
            else:
                dic[str(cursor.value)] += 1
                pre = cursor
                cursor = cursor.next

    def reverse(self):
        """
        逆序  ?????????????????????????????
        :return:
        """
        if self.root == None:
            return None
        if self.length == 1:
            return None
        else:
            post = None
            pre = None
            cursor = self.root
            while cursor != None:
                post = cursor.next
                cursor.next = pre
                pre = cursor
                cursor = post
            self.root = pre

    def delLinkedList(self):
        """
        删除链表
        :return:
        """
        if self.root == None:
            return None
        else:
            self.root = None

    def getNode(self, index):
        if self.root == None:
            return None
        if index == 0:
            return self.root
        if index < 0 or index > self.length:
            print('Index 非法, 索引不在范围内')
        else:
            counter = 0
            cursor = self.root
            while cursor != None:
                if counter == index:
                    return cursor
                cursor = cursor.next
                counter += 1


if __name__ == '__main__':
    # ------创建链表-------
    linkedlist = LinkedList()
    # ------添加节点-------
    linkedlist.addNode(1)
    linkedlist.prepend(0)
    linkedlist.insert(0, -1)
    linkedlist.insert(2, -3)
    linkedlist.print()

    # ------测试插入节点-------
    linkedlist.insert(1, 6)
    linkedlist.print()

    # ------测试删除节点-------
    linkedlist.delNode(3)
    linkedlist.print()

    linkedlist.addNode(0)
    linkedlist.print()

    # ------测试删除某值的节点-------
    linkedlist.delValue(0)
    linkedlist.print()

    # ------测试获取节点的值-------
    i = 1
    value = linkedlist.getValue(i)
    print(i, '处的值为: ', value)

    # ------测试查找某值的索引-------
    linkedlist.prepend(0)
    linkedlist.addNode(1)
    linkedlist.addNode(6)
    linkedlist.addNode(-3)
    linkedlist.print()
    print(linkedlist.getValueIndex(-3))

    # ------测试获取最后一个值-------
    linkedlist.print()
    value = linkedlist.peek()
    print('链表最后一个值为: ', value)

    # ------测试获取并删除最后一个值-------
    value = linkedlist.pop()
    print('链表最后一个值为: ', value)
    linkedlist.print()

    # ------测试反转-------
    linkedlist.reverse()
    print('反转后: ', end='')
    linkedlist.print()

    # ------测试修改-------
    linkedlist.print()
    linkedlist.updateNode(5, 7)
    print('修改后: ', end='')
    linkedlist.print()

    # ------测试删除重复-------
    # linkedlist.print()
    # linkedlist.delDuplecate()
    # linkedlist.print()

    # -----获取节点-------
    node1 = linkedlist.getNode(1)
    linkedlist.print()
    print(node1.next.value)

    # ------清空链表-------
    linkedlist.delLinkedList()
    linkedlist.print()

    # ------测试长度-------
    print('链表长度: ', linkedlist.length)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

C++ STL之set的基本操作

set是集合,虽然也存在键值和实值,不过两者根本就是同一个值,键值的设置完全就是为了满足红黑树的底层结构,set操作与map很像不过也有些不同。 1、 set迭...

2865
来自专栏Rovo89

JavaScript闭包与箭头函数

912
来自专栏有趣的Python

6-Java常用工具类-集合排序

http://www.runoob.com/java/java-generics.html

893
来自专栏谈补锅

C语言之指针变量

  4、指向常量的常量指针:有2个const修改,既不能间接修改变量的值,也不可重新赋值新变量地址

2793
来自专栏葡萄城控件技术团队

JavaScript 常用功能总结

小编吐血整理加上翻译,太辛苦了~求赞! 本文主要总结了JavaScript 常用功能总结,如一些常用的JS 对象,基本数据结构,功能函数等,还有一些常用的设计模...

21410
来自专栏IMWeb前端团队

JSON Schema 参考书

本文作者:IMWeb 孙世吉 原文出处:IMWeb社区 未经同意,禁止转载 1 简介 JSON 模式(JSON Schema)是一种基于 JSON 格...

37510
来自专栏smy

php unset对json_encode的影响

发现对一个数组unset前后,变量的类型变化了,unset前是数组,unset后是对象

801
来自专栏swag code

Master Method Restated-主项定理-递归时间复杂度

比较n^log b (a)与Θ(h(n)) 的大小(Θ的含义和“等于”类似,而大O的含义和“小于等于”类似,感觉好像这里都可以用):

1142
来自专栏python学习路

四、正则表达式re模块 常用的匹配规则:Python 的 re 模块也可以直接用re.match(),re.search(),re.findall(),re.finditer(),re.sub()

什么是正则表达式 正则表达式,又称规则表达式,通常被用来检索、替换那些符合某个模式(规则)的文本。 正则表达式是对字符串操作的一种逻辑公式,就是用事先定义好...

3734
来自专栏Python爱好者

Java基础笔记15

1658

扫码关注云+社区

领取腾讯云代金券