Python链接列表

Question

在python中使用链表最简单的方法是什么？在方案中,链接列表简单地定义'(1 2 3 4 5).事实上,Python的列表[1, 2, 3, 4, 5]和元组(1, 2, 3, 4, 5)并不是链表,链表有一些很好的属性,例如常量时间连接,并且能够引用它们的不同部分.让它们一成不变,它们真的很容易合作!

Answer 1

对于某些需求,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

Answer 2

我前几天写了这篇文章

#! /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()

Answer 3

以下是基于Martinv.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表示,或

• 包含货物对象和对链接列表的引用的节点.

  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")
  

Answer 4

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

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__()

Answer 5

不可变列表最好通过两元组表示,None表示NIL.要允许简单地制定此类列表,您可以使用此功能:

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

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

Answer 6

这是链表类的稍微复杂的版本,具有与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

Answer 7

llist - Python的链接列表数据类型

llist模块实现链表数据结构.它支持双向链表,即dllist单链接数据结构sllist.

dllist对象

该对象表示双向链表数据结构.

first

dllistnode列表中的第一个对象.None如果列表为空.

last

dllistnode列表中的最后一个对象.如果列表为空,则为无.

dllist对象还支持以下方法:

append(x)

添加x到列表的右侧并返回插入dllistnode.

appendleft(x)

添加x到列表的左侧并返回插入dllistnode.

appendright(x)

添加x到列表的右侧并返回插入dllistnode.

clear()

从列表中删除所有节点.

extend(iterable)

将元素附加iterable到列表的右侧.

extendleft(iterable)

将元素附加iterable到列表的左侧.

extendright(iterable)

将元素附加iterable到列表的右侧.

insert(x[, before])

x如果before未指定,则添加到列表的右侧,或插入x到左侧dllistnode before.返回插入dllistnode.

nodeat(index)

返回节点(类型dllistnode)at index.

pop()

从列表的右侧删除并返回元素的值.

popleft()

从列表的左侧删除并返回元素的值.

popright()

从列表的右侧删除并返回元素的值

remove(node)

node从列表中删除并返回存储在其中的元素.

dllistnode 对象

类 llist.dllistnode([value])

返回一个新的双向链表节点,初始化(可选)value.

dllistnode 对象提供以下属性:

next

列表中的下一个节点.该属性是只读的.

prev

列表中的上一个节点.该属性是只读的.

value

存储在此节点中的值. 从此参考编译而来

sllist

class llist.sllist([iterable]) 返回一个用元素初始化的新的单链表iterable.如果未指定iterable,则new sllist为空.

为此sllist对象定义了一组类似的属性和操作.有关更多信息,请参阅此参考.