关于python3实现单向链表,以及链表反转的问题

起因:

最近看到了一个python3的笔试题目,说是实现一个单向链表,并实现反转方法。 说心里话,看到这样的题目,很无语。因为我觉得这应该是C语言做的事情,但是仔细一想,兴许这道题是为了考察面试者的算法能力呢?所以就自己实现了一下,顺便练习了一下pytest模块的使用。

talk is cheap,show me the code

#! /usr/bin/python3
# -*- coding:utf-8 -*-
# file: linklist.py
# author: wangchenxi
# mail: wongchenxi@icloud.com
# brief:
# version: 0.1.00
# Create Time:2019-11-12 17:03:51
# Last Update: 2019-11-13 00时14分52秒


class Node(object):

    def __init__(self, val=None, *args, **kwarg):
        self.value = val
        self.next = None


class LinkList(object):

    def __init__(self, *args, **kwarg):
        self.__head = None

    def __len__(self):
        size = 0
        t = self.__head
        while t:
            t = t.next
            size += 1
        return size

    def tolist(self):
        t = self.__head
        index = 0
        ret = []
        while t:
            ret.append(t.value)
            t = t.next
            index += 1
        return ret

    def fromlist(self, l):
        n = 0
        length = len(l)
        self.clear()
        while n < length:
            self.append(Node(l[n]))
            n += 1

    def travel(self):
        print(self.tolist())

    def push(self, n):
        if self.__head:
            n.next = self.__head
            self.__head = n
        else:
            self.__head = n

    def append(self, n):
        if not self.__head:
            self.__head = n
            return None
        index = 0
        np = self.__head
        while np:
            index += 1
            pre = np
            np = np.next
        pre.next = n

    def insert(self, pos, n):
        if not pos:
            return self.push(n)
        if pos > len(self)-1:
            return self.append(n)
        t = pos
        tn = self.__head
        fn = tn
        while t:
            fn = tn
            tn = tn.next
            t -= 1
        n.next = tn
        fn.next = n

    def pop(self, index=0):
        if index > len(self) - 1:
            return
        dn = self.__head
        fn = None
        while index:
            fn = dn
            dn = dn.next
            index -= 1
        else:
            if not fn:
                nn = self.__head.next
                self.__head.next = None
                ret = self.__head
                self.__head = nn
            else:
                nn = dn.next
                dn.next = None
                ret = dn
                fn.next = nn
        return ret

    def delete(self, index=0):
        self.pop(index)

    def clear(self):
        while len(self):
            self.delete()

    def update(self, pos, val):
        if pos > len(self) - 1:
            return
        sn = self.__head
        while pos:
            sn = sn.next
            pos -= 1
        else:
            sn.value = val

    def index(self, val):
        sn = self.__head
        ind = 0
        while sn and sn.value != val:
            ind += 1
            sn = sn.next
        if sn:
            return ind

    def reverse(self):
        _ = self.tolist()
        _ = _[-1::-1]
        self.fromlist(_)

    def myreverse(self):
        length = len(self)
        if length < 2:
            return
        ind = 0
        last = length - 1
        while ind < length:
            ret = self.pop(last)
            self.insert(ind, ret)
            ind += 1

pytest 模块测试

#! /usr/bin/python3
# -*- coding:utf-8 -*-
# file: test_linklist.py
# author: wangchenxi
# mail: wongchenxi@icloud.com
# brief:
# version: 0.1.00
# Create Time:2019-11-12 21:17:56
# Last Update: 2019-11-13 00时13分09秒
from linklist import Node, LinkList


def test_append():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    assert var_l.tolist() == r


def test_insert():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    var_l.insert(3, Node(20))
    r.insert(3, 20)
    assert var_l.tolist() == r


def test_delete():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    var_l.delete()
    r.pop(0)
    assert var_l.tolist() == r


def test_delete1():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    var_l.delete(3)
    r.pop(3)
    assert var_l.tolist() == r


def test_clear():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    var_l.clear()
    r.clear()
    assert var_l.tolist() == r


def test_update():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    var_l.update(4, 100)
    r[4] = 100
    assert var_l.tolist() == r


def test_index():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    assert var_l.index(6) == r.index(6)


def test_reverse():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    var_l.reverse()
    r = r[-1::-1]
    assert var_l.tolist() == r


def test_myreverse():
    var_l = LinkList()
    r = list()
    for i in range(10):
        var_l.append(Node(i))
        r.append(i)
    var_l.myreverse()
    r = r[-1::-1]
    assert var_l.tolist() == r

运行测试案例

pip3 install pytest
pytest -v test_linklist.py

测试案例执行结果

============================================================ test session starts ============================================================
platform linux -- Python 3.6.9, pytest-5.2.2, py-1.8.0, pluggy-0.13.0 -- /usr/bin/python3
cachedir: .pytest_cache
rootdir: /home/wangchenxi/for_find_work/datastruct
plugins: pep8-1.0.6
collected 9 items                                                                                                                           

test_linklist.py::test_append PASSED                                                                                                  [ 11%]
test_linklist.py::test_insert PASSED                                                                                                  [ 22%]
test_linklist.py::test_delete PASSED                                                                                                  [ 33%]
test_linklist.py::test_delete1 PASSED                                                                                                 [ 44%]
test_linklist.py::test_clear PASSED                                                                                                   [ 55%]
test_linklist.py::test_update PASSED                                                                                                  [ 66%]
test_linklist.py::test_index PASSED                                                                                                   [ 77%]
test_linklist.py::test_reverse PASSED                                                                                                 [ 88%]
test_linklist.py::test_myreverse PASSED                                                                                               [100%]

============================================================= 9 passed in 0.05s =============================================================

版权声明:除特别注明外,本站所有文章均为王晨曦个人站点原创

转载请注明:出处来自王晨曦个人站点 » 关于python3实现单向链表,以及链表反转的问题

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注