8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

如何在 Python 中使用链表?

aphoria 2月前

302 0

在 Python 中使用链表的最简单方法是什么?在 Scheme 中,链表的定义很简单,即“(1 2 3 4 5)。Python 的列表 [1, 2, 3, 4, 5] 和元组 (1, 2, 3, 4, 5) 实际上并不像......

在 Python 中使用链表的最简单方法是什么?在 Scheme 中,链表的定义很简单 '(1 2 3 4 5) .

Python 的列表 [1, 2, 3, 4, 5] 和元组 (1, 2, 3, 4, 5) 并不是链表,链表具有一些不错的特性,例如常量时间连接,以及能够引用其中的不同部分。如果使它们不可变,那么它们就真的很容易使用!

帖子版权声明 1、本帖标题:如何在 Python 中使用链表?
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由aphoria在本站《performance》版块原创发布, 转载请注明出处!
最新回复 (0)
  • 以下是一些基于 Martin v. Löwis 表示的 :

    cons   = lambda el, lst: (el, lst)
    mklist = lambda *args: reduce(lambda lst, el: cons(el, lst), reversed(args), None)
    car = lambda lst: lst[0] if lst else lst
    cdr = lambda lst: lst[1] if lst else lst
    nth = lambda n, lst: nth(n-1, cdr(lst)) if n > 0 else car(lst)
    length  = lambda lst, count=0: length(cdr(lst), count+1) if lst else count
    begin   = lambda *args: args[-1]
    display = lambda lst: begin(w("%s " % car(lst)), display(cdr(lst))) if lst else w("nil\n")
    

    在哪里 w = sys.stdout.write

    尽管双向链表在 Raymond Hettinger 的 有序集合配方 ,但单向链表在 Python 中没有实际价值。

    从未 在 Python 中使用单链表来解决任何问题。

    Thomas Watnedal 推荐了 一个很好的教育资源 《如何像计算机科学家一样思考》,第 17 章:链表 :

    链接列表可以是:

    • 空列表,用 None 表示,或者
    • p6

      class Node:   def __init__(self, cargo=None, next=None):     self.car = cargo     self.cdr = next      def __str__(self):     return str(self.car)def display(lst):  if lst:    w("%s " % lst)    display(lst.cdr)  else:    w("nil\n")
  • 你说:除了教育目的之外,你从未在 Python 中使用单链表解决任何问题。这对你来说很好 :-) 但我可以向你保证:在现实世界中,确实存在一些问题,链表将提供理想的解决方案 :-) 这就是我首先在 StackOverflow 上搜索链表的原因 :-)

  • ndm 2月前 0 只看Ta
    引用 4

    @RegisMay:您介意提供一个具体的实际代码示例的链接吗?(注意:它应该是“Python 中的单链表”“在现实世界中”:描述您的示例的好处,例如可读性、性能或您选择的其他“实际价值”)。我过去也提出过类似的请求:8 年来,除了 Raymond Hettinger 的有序集配方中使用的双向链表外,没有其他链接——也许,这可以解释为只有刚接触 Python 的程序员才会读到这个问题——您的意见将非常有价值,非常感谢。

  • 哦,抱歉。我不是英语母语人士,并且将“单链表”与“单个链接列表”混淆了。尽管如此,我需要一个(双)链表 - 它在 Python 中不存在。双端队列没有帮助,因为我需要直接访问每个单个元素,而无需遍历所有元素。我的目标是:我想实现缓存。尽管如此:如果我的英语水平不高导致我的评论不合适,请删除这些评论。如有不便,敬请原谅。

  • 与双向链表或数组(Python 内部用于列表)相比,单链表的一个实际优势是两个链表可以共享尾部。这对于需要保存先前迭代的值的动态算法非常有用,共享列表尾部可以将内存复杂度从二次方降低到线性,并消除复制造成的时间开销。

  • 该 rosettacode 链接是一个真实世界示例,它使用模拟链表代替实际链表。查看它,重写它以使用实际链表,以提高清晰度和可读性,这就是使用链表改进现有代码的真实世界示例。其次,最长递增子序列算法在现实世界中(在统计学中)使用,所以就是这样。QED :)。除此之外,我们只是同意不同意。:)

  • 对于某些需求, deque 也可能有用。您可以以 O(1) 成本在双端队列的两端添加和删除项目。

    from collections import deque
    d = deque([1,2,3,4])
    
    print d
    for x in d:
        print x
    print d.pop(), d
    
  • 虽然双端队列是一种有用的数据类型,但它不是链表(尽管它是在 C 级别使用双向链表实现的)。因此它回答了“在 Python 中,你会用什么来代替链表?”这个问题,在这种情况下,第一个答案应该是(对于某些需求)普通的 Python 列表(它也不是链表)。

  • 引用 10

    @JFSebastian:我几乎同意你的观点 :) 我认为这个问题的答案是:“在其他语言中,使用链表解决问题的 Python 方式是什么?”并不是说链表没有用,只是双端队列不起作用的问题非常罕见。

  • 它与“Pythonic”无关:链表是一种与双端队列不同的数据结构,并且在两者支持的各种操作中,它们的运行时间不同。

  • @dimo414:链接列表通常禁止索引(没有 linked_list[n]),因为它是 O(n)。双端队列允许它,并在 O(1) 中执行它。但是,给定一个迭代器到列表中,链接列表可以允许 O(1) 插入和删除,而双端队列不能(它是 O(n),就像一个向量)。(除了在前端和末端,双端队列和链接列表都是 O(1)。(虽然双端队列可能是摊销的 O(1)。链接列表不是。)

  • 引用 13

    @MadPhysicist \'即使名称不同,它 [deque] 在几乎所有方面都表现得像一个链接列表。\' — 它要么是错误的,要么是毫无意义的:它是错误的,因为链接列表可能为时间复杂度提供不同的保证,例如,您可以在 O(1) 中从链接列表中删除一个元素(已知位置),而 deque 不保证这一点(它是 O(n))。如果 \'几乎所有方式\' 允许忽略大 O 中的差异,那么您的陈述毫无意义,因为如果不是为了 pop(0)、insert(0,v) 大 O 保证,我们可以使用 Python 内置列表作为 deque。

  • 我前几天写了这个

    #! /usr/bin/env python
    
    class Node(object):
        def __init__(self):
            self.data = None # contains the data
            self.next = None # contains the reference to the next node
    
    
    class LinkedList:
        def __init__(self):
            self.cur_node = None
    
        def add_node(self, data):
            new_node = Node() # create a new node
            new_node.data = data
            new_node.next = self.cur_node # link the new node to the 'previous' node.
            self.cur_node = new_node #  set the current node to the new one.
    
        def list_print(self):
            node = self.cur_node # cant point to ll!
            while node:
                print node.data
                node = node.next
    
    
    
    ll = LinkedList()
    ll.add_node(1)
    ll.add_node(2)
    ll.add_node(3)
    
    ll.list_print()
    
  • @locoboy 执行该操作的代码在逻辑上与 list_print() 中的代码类似。

  • 可接受的答案相当复杂。这是一个更标准的设计:

    L = LinkedList()
    L.insert(1)
    L.insert(1)
    L.insert(2)
    L.insert(4)
    print L
    L.clear()
    print L
    

    它是一个简单的 LinkedList 类,基于简单的 C++ 设计和 第 17 章:链表 ,由 Thomas Watnedal .

    class Node:
        def __init__(self, value = None, next = None):
            self.value = value
            self.next = next
    
        def __str__(self):
            return 'Node ['+str(self.value)+']'
    
    class LinkedList:
        def __init__(self):
            self.first = None
            self.last = None
    
        def insert(self, x):
            if self.first == None:
                self.first = Node(x, None)
                self.last = self.first
            elif self.last == self.first:
                self.last = Node(x, None)
                self.first.next = self.last
            else:
                current = Node(x, None)
                self.last.next = current
                self.last = current
    
        def __str__(self):
            if self.first != None:
                current = self.first
                out = 'LinkedList [\n' +str(current.value) +'\n'
                while current.next != None:
                    current = current.next
                    out += str(current.value) + '\n'
                return out + ']'
            return 'LinkedList []'
    
        def clear(self):
            self.__init__()
    
  • 我喜欢这个答案。有一点需要注意,我认为 X is None 比 == 更受欢迎。.com/a/2988117/1740227

  • 插入的第二个分支不是第三个分支的特殊情况吗,这样您就可以完全删除 elif 子句?

  • 不可变列表最好通过二元组来表示,其中 None 表示 NIL。为了允许简单地制定此类列表,您可以使用此函数:

    def mklist(*args):
        result = None
        for element in reversed(args):
            result = (element, result)
        return result
    

    为了使用这样的列表,我宁愿提供整个 LISP 函数集合(即第一个、第二个、第 n 个等等),而不是引入方法。

  • 这是链接列表类的一个稍微复杂一点的版本,具有与 Python 序列类型类似的接口(即支持索引、切片、与任意序列连接等)。它应该具有 O(1) 前置功能,除非需要,否则不会复制数据,并且可以与元组互换使用。

    它不会像 lisp cons 单元那样节省空间或时间,因为 python 类显然更重一些(您可以使用 \' __slots__ = '_head','_tail' \' 稍微改进一下以减少内存使用量)。但是它将具有所需的大 O 性能特征。

    使用示例:

    >>> l = LinkedList([1,2,3,4])
    >>> l
    LinkedList([1, 2, 3, 4])
    >>> l.head, l.tail
    (1, LinkedList([2, 3, 4]))
    
    # Prepending is O(1) and can be done with:
    LinkedList.cons(0, l)
    LinkedList([0, 1, 2, 3, 4])
    # Or prepending arbitrary sequences (Still no copy of l performed):
    [-1,0] + l
    LinkedList([-1, 0, 1, 2, 3, 4])
    
    # Normal list indexing and slice operations can be performed.
    # Again, no copy is made unless needed.
    >>> l[1], l[-1], l[2:]
    (2, 4, LinkedList([3, 4]))
    >>> assert l[2:] is l.next.next
    
    # For cases where the slice stops before the end, or uses a
    # non-contiguous range, we do need to create a copy.  However
    # this should be transparent to the user.
    >>> LinkedList(range(100))[-10::2]
    LinkedList([90, 92, 94, 96, 98])
    

    执行:

    import itertools
    
    class LinkedList(object):
        """Immutable linked list class."""
    
        def __new__(cls, l=[]):
            if isinstance(l, LinkedList): return l # Immutable, so no copy needed.
            i = iter(l)
            try:
                head = i.next()
            except StopIteration:
                return cls.EmptyList   # Return empty list singleton.
    
            tail = LinkedList(i)
    
            obj = super(LinkedList, cls).__new__(cls)
            obj._head = head
            obj._tail = tail
            return obj
    
        @classmethod
        def cons(cls, head, tail):
            ll =  cls([head])
            if not isinstance(tail, cls):
                tail = cls(tail)
            ll._tail = tail
            return ll
    
        # head and tail are not modifiable
        @property  
        def head(self): return self._head
    
        @property
        def tail(self): return self._tail
    
        def __nonzero__(self): return True
    
        def __len__(self):
            return sum(1 for _ in self)
    
        def __add__(self, other):
            other = LinkedList(other)
    
            if not self: return other   # () + l = l
            start=l = LinkedList(iter(self))  # Create copy, as we'll mutate
    
            while l:
                if not l._tail: # Last element?
                    l._tail = other
                    break
                l = l._tail
            return start
    
        def __radd__(self, other):
            return LinkedList(other) + self
    
        def __iter__(self):
            x=self
            while x:
                yield x.head
                x=x.tail
    
        def __getitem__(self, idx):
            """Get item at specified index"""
            if isinstance(idx, slice):
                # Special case: Avoid constructing a new list, or performing O(n) length 
                # calculation for slices like l[3:].  Since we're immutable, just return
                # the appropriate node. This becomes O(start) rather than O(n).
                # We can't do this for  more complicated slices however (eg [l:4]
                start = idx.start or 0
                if (start >= 0) and (idx.stop is None) and (idx.step is None or idx.step == 1):
                    no_copy_needed=True
                else:
                    length = len(self)  # Need to calc length.
                    start, stop, step = idx.indices(length)
                    no_copy_needed = (stop == length) and (step == 1)
    
                if no_copy_needed:
                    l = self
                    for i in range(start): 
                        if not l: break # End of list.
                        l=l.tail
                    return l
                else:
                    # We need to construct a new list.
                    if step < 1:  # Need to instantiate list to deal with -ve step
                        return LinkedList(list(self)[start:stop:step])
                    else:
                        return LinkedList(itertools.islice(iter(self), start, stop, step))
            else:       
                # Non-slice index.
                if idx < 0: idx = len(self)+idx
                if not self: raise IndexError("list index out of range")
                if idx == 0: return self.head
                return self.tail[idx-1]
    
        def __mul__(self, n):
            if n <= 0: return Nil
            l=self
            for i in range(n-1): l += self
            return l
        def __rmul__(self, n): return self * n
    
        # Ideally we should compute the has ourselves rather than construct
        # a temporary tuple as below.  I haven't impemented this here
        def __hash__(self): return hash(tuple(self))
    
        def __eq__(self, other): return self._cmp(other) == 0
        def __ne__(self, other): return not self == other
        def __lt__(self, other): return self._cmp(other) < 0
        def __gt__(self, other): return self._cmp(other) > 0
        def __le__(self, other): return self._cmp(other) <= 0
        def __ge__(self, other): return self._cmp(other) >= 0
    
        def _cmp(self, other):
            """Acts as cmp(): -1 for self<other, 0 for equal, 1 for greater"""
            if not isinstance(other, LinkedList):
                return cmp(LinkedList,type(other))  # Arbitrary ordering.
    
            A, B = iter(self), iter(other)
            for a,b in itertools.izip(A,B):
               if a<b: return -1
               elif a > b: return 1
    
            try:
                A.next()
                return 1  # a has more items.
            except StopIteration: pass
    
            try:
                B.next()
                return -1  # b has more items.
            except StopIteration: pass
    
            return 0  # Lists are equal
    
        def __repr__(self):
            return "LinkedList([%s])" % ', '.join(map(repr,self))
    
    class EmptyList(LinkedList):
        """A singleton representing an empty list."""
        def __new__(cls):
            return object.__new__(cls)
    
        def __iter__(self): return iter([])
        def __nonzero__(self): return False
    
        @property
        def head(self): raise IndexError("End of list")
    
        @property
        def tail(self): raise IndexError("End of list")
    
    # Create EmptyList singleton
    LinkedList.EmptyList = EmptyList()
    del EmptyList
    
返回
作者最近主题: