在python中使用链表最简单的方法是什么？在方案中,链接列表简单地定义'(1 2 3 4 5).事实上,Python的列表[1, 2, 3, 4, 5]和元组(1, 2, 3, 4, 5)并不是链表,链表有一些很好的属性,例如常量时间连接,并且能够引用它们的不同部分.让它们一成不变,它们真的很容易合作!
对于某些需求,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
我前几天写了这篇文章
#! /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()
以下是基于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")
接受的答案相当复杂.这是一个更标准的设计:
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__()
不可变列表最好通过两元组表示,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 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
llist模块实现链表数据结构.它支持双向链表,即dllist单链接数据结构sllist.
该对象表示双向链表数据结构.
firstdllistnode列表中的第一个对象.None如果列表为空.
lastdllistnode列表中的最后一个对象.如果列表为空,则为无.
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存储在此节点中的值. 从此参考编译而来
sllistclass llist.sllist([iterable])
返回一个用元素初始化的新的单链表iterable.如果未指定iterable,则new sllist为空.
为此sllist对象定义了一组类似的属性和操作.有关更多信息,请参阅此参考.
京公网安备 11010802040832号 | 京ICP备19059560号-6 