Pythonでリンクリストを使用する最も簡単な方法は何ですか? スキームでは、連結リストは単純に で定義され'(1 2 3 4 5)ます。Python のリスト 、[1, 2, 3, 4, 5]およびタプル は(1, 2, 3, 4, 5)、実際には連結リストではありません。連結リストには、一定時間の連結や、それらの個別の部分を参照できるなどの優れた特性があります。それらを不変にすると、操作が本当に簡単になります!
326454 次
29 に答える
160
一部のニーズでは、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
于 2008-11-11T21:45:30.850 に答える
72
これは先日書きました
#! /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()
于 2008-11-11T07:54:49.060 に答える
70
以下は、 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
二重連結リストは、レイモンド ヘッティンガーの順序集合レシピで有名に使用されていますが、単方向連結リストは Python では実用的な価値がありません。
教育以外の問題で、Python で単一リンク リストを使用したことはありません。
Thomas Watnedalは、優れた教育リソースを提案しましたHow to Think Like a Computer Scientist, Chapter 17: Linked lists :
リンクされたリストは次のいずれかです。
- None で表される空のリスト、または
cargo オブジェクトとリンクされたリストへの参照を含むノード。
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")
于 2008-11-12T11:10:15.687 に答える
38
受け入れられた答えはかなり複雑です。より標準的なデザインを次に示します。
L = LinkedList()
L.insert(1)
L.insert(1)
L.insert(2)
L.insert(4)
print L
L.clear()
print L
これは、Thomas Watnedalが推奨する、単純な C++ 設計と第 17 章: リンクされたリストLinkedListに基づく単純なクラスです。
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__()
于 2010-08-21T16:04:51.867 に答える
17
不変リストは、NIL を表す None を使用して、2 つのタプルで表現するのが最適です。このようなリストを簡単に作成できるようにするには、次の関数を使用できます。
def mklist(*args):
result = None
for element in reversed(args):
result = (element, result)
return result
このようなリストを操作するには、メソッドを導入するよりも、LISP 関数のコレクション全体 (つまり、first、second、nth など) を提供したいと思います。
于 2008-11-11T07:54:20.887 に答える
13
これはリンク リスト クラスのもう少し複雑なバージョンで、Python のシーケンス型と同様のインターフェイスを備えています (つまり、インデックス作成、スライス、任意のシーケンスとの連結などをサポートしています)。O(1) プリペンドが必要で、必要でない限りデータをコピーせず、タプルとかなり互換的に使用できます。
Lisp のコンス セルほどスペースや時間の効率は高くありません。Python のクラスは明らかにもう少し重いためです (__slots__ = '_head','_tail'メモリ使用量を減らすために " " を使用すると少し改善できます)。ただし、必要な Big 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
于 2008-11-11T15:59:46.617 に答える
2
この追加機能はNick Stinematesに基づいています
def add_node_at_end(self, data):
new_node = Node()
node = self.curr_node
while node:
if node.next == None:
node.next = new_node
new_node.next = None
new_node.data = data
node = node.next
彼が持っている方法は、最初に新しいノードを追加しますが、通常は最後に新しいノードを追加する多くの実装を見てきましたが、それは楽しいことです。
于 2011-07-12T01:37:41.017 に答える
2
以下は私が思いついたものです。このスレッドの Riccardo C.に似ていますが、番号を逆ではなく順番に出力する点が異なります。また、通常の Python リストと同じようにリストを出力するために、LinkedList オブジェクトを Python Iterator にしました。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.head = None
self.curr = None
self.tail = None
def __iter__(self):
return self
def next(self):
if self.head and not self.curr:
self.curr = self.head
return self.curr
elif self.curr.next:
self.curr = self.curr.next
return self.curr
else:
raise StopIteration
def append(self, data):
n = Node(data)
if not self.head:
self.head = n
self.tail = n
else:
self.tail.next = n
self.tail = self.tail.next
# Add 5 nodes
ll = LinkedList()
for i in range(1, 6):
ll.append(i)
# print out the list
for n in ll:
print n
"""
Example output:
$ python linked_list.py
1
2
3
4
5
"""
于 2013-03-03T05:03:45.403 に答える
1
class LL(object):
def __init__(self,val):
self.val = val
self.next = None
def pushNodeEnd(self,top,val):
if top is None:
top.val=val
top.next=None
else:
tmp=top
while (tmp.next != None):
tmp=tmp.next
newNode=LL(val)
newNode.next=None
tmp.next=newNode
def pushNodeFront(self,top,val):
if top is None:
top.val=val
top.next=None
else:
newNode=LL(val)
newNode.next=top
top=newNode
def popNodeFront(self,top):
if top is None:
return
else:
sav=top
top=top.next
return sav
def popNodeEnd(self,top):
if top is None:
return
else:
tmp=top
while (tmp.next != None):
prev=tmp
tmp=tmp.next
prev.next=None
return tmp
top=LL(10)
top.pushNodeEnd(top, 20)
top.pushNodeEnd(top, 30)
pop=top.popNodeEnd(top)
print (pop.val)
于 2014-06-21T14:32:51.407 に答える
1
class LinkedStack:
'''LIFO Stack implementation using a singly linked list for storage.'''
_ToList = []
#---------- nested _Node class -----------------------------
class _Node:
'''Lightweight, nonpublic class for storing a singly linked node.'''
__slots__ = '_element', '_next' #streamline memory usage
def __init__(self, element, next):
self._element = element
self._next = next
#--------------- stack methods ---------------------------------
def __init__(self):
'''Create an empty stack.'''
self._head = None
self._size = 0
def __len__(self):
'''Return the number of elements in the stack.'''
return self._size
def IsEmpty(self):
'''Return True if the stack is empty'''
return self._size == 0
def Push(self,e):
'''Add element e to the top of the Stack.'''
self._head = self._Node(e, self._head) #create and link a new node
self._size +=1
self._ToList.append(e)
def Top(self):
'''Return (but do not remove) the element at the top of the stack.
Raise exception if the stack is empty
'''
if self.IsEmpty():
raise Exception('Stack is empty')
return self._head._element #top of stack is at head of list
def Pop(self):
'''Remove and return the element from the top of the stack (i.e. LIFO).
Raise exception if the stack is empty
'''
if self.IsEmpty():
raise Exception('Stack is empty')
answer = self._head._element
self._head = self._head._next #bypass the former top node
self._size -=1
self._ToList.remove(answer)
return answer
def Count(self):
'''Return how many nodes the stack has'''
return self.__len__()
def Clear(self):
'''Delete all nodes'''
for i in range(self.Count()):
self.Pop()
def ToList(self):
return self._ToList
于 2016-10-16T16:30:52.460 に答える
1
リンク リスト クラス
class LinkedStack:
# Nested Node Class
class Node:
def __init__(self, element, next):
self.__element = element
self.__next = next
def get_next(self):
return self.__next
def get_element(self):
return self.__element
def __init__(self):
self.head = None
self.size = 0
self.data = []
def __len__(self):
return self.size
def __str__(self):
return str(self.data)
def is_empty(self):
return self.size == 0
def push(self, e):
newest = self.Node(e, self.head)
self.head = newest
self.size += 1
self.data.append(newest)
def top(self):
if self.is_empty():
raise Empty('Stack is empty')
return self.head.__element
def pop(self):
if self.is_empty():
raise Empty('Stack is empty')
answer = self.head.element
self.head = self.head.next
self.size -= 1
return answer
使用法
from LinkedStack import LinkedStack
x = LinkedStack()
x.push(10)
x.push(25)
x.push(55)
for i in range(x.size - 1, -1, -1):
print '|', x.data[i].get_element(), '|' ,
#next object
if x.data[i].get_next() == None:
print '--> None'
else:
print x.data[i].get_next().get_element(), '-|----> ',
出力
| 55 | 25 -|----> | 25 | 10 -|----> | 10 | --> None
于 2016-11-30T13:00:26.607 に答える
1
不変のリンクされたリストを使用する場合は、Python のタプルを直接使用することを検討してください。
ls = (1, 2, 3, 4, 5)
def first(ls): return ls[0]
def rest(ls): return ls[1:]
本当に簡単で、len(ls)、x in ls などの追加の関数を保持できます。
于 2008-11-11T10:46:43.833 に答える
1
Python 2.x および 3.x の単一リンク リスト クラスをhttps://pypi.python.org/pypi/linked_list_mod/に配置しました。
CPython 2.7、CPython 3.4、Pypy 2.3.1、Pypy3 2.3.1、および Jython 2.7b2 でテストされており、優れた自動テスト スイートが付属しています。
また、LIFO および FIFO クラスも含まれます。
ただし、それらは不変ではありません。
于 2014-07-28T01:48:23.687 に答える
0
以下の実装は、法案を非常に優雅に満たすと思います。
'''singly linked lists, by Yingjie Lan, December 1st, 2011'''
class linkst:
'''Singly linked list, with pythonic features.
The list has pointers to both the first and the last node.'''
__slots__ = ['data', 'next'] #memory efficient
def __init__(self, iterable=(), data=None, next=None):
'''Provide an iterable to make a singly linked list.
Set iterable to None to make a data node for internal use.'''
if iterable is not None:
self.data, self.next = self, None
self.extend(iterable)
else: #a common node
self.data, self.next = data, next
def empty(self):
'''test if the list is empty'''
return self.next is None
def append(self, data):
'''append to the end of list.'''
last = self.data
self.data = last.next = linkst(None, data)
#self.data = last.next
def insert(self, data, index=0):
'''insert data before index.
Raise IndexError if index is out of range'''
curr, cat = self, 0
while cat < index and curr:
curr, cat = curr.next, cat+1
if index<0 or not curr:
raise IndexError(index)
new = linkst(None, data, curr.next)
if curr.next is None: self.data = new
curr.next = new
def reverse(self):
'''reverse the order of list in place'''
current, prev = self.next, None
while current: #what if list is empty?
next = current.next
current.next = prev
prev, current = current, next
if self.next: self.data = self.next
self.next = prev
def delete(self, index=0):
'''remvoe the item at index from the list'''
curr, cat = self, 0
while cat < index and curr.next:
curr, cat = curr.next, cat+1
if index<0 or not curr.next:
raise IndexError(index)
curr.next = curr.next.next
if curr.next is None: #tail
self.data = curr #current == self?
def remove(self, data):
'''remove first occurrence of data.
Raises ValueError if the data is not present.'''
current = self
while current.next: #node to be examined
if data == current.next.data: break
current = current.next #move on
else: raise ValueError(data)
current.next = current.next.next
if current.next is None: #tail
self.data = current #current == self?
def __contains__(self, data):
'''membership test using keyword 'in'.'''
current = self.next
while current:
if data == current.data:
return True
current = current.next
return False
def __iter__(self):
'''iterate through list by for-statements.
return an iterator that must define the __next__ method.'''
itr = linkst()
itr.next = self.next
return itr #invariance: itr.data == itr
def __next__(self):
'''the for-statement depends on this method
to provide items one by one in the list.
return the next data, and move on.'''
#the invariance is checked so that a linked list
#will not be mistakenly iterated over
if self.data is not self or self.next is None:
raise StopIteration()
next = self.next
self.next = next.next
return next.data
def __repr__(self):
'''string representation of the list'''
return 'linkst(%r)'%list(self)
def __str__(self):
'''converting the list to a string'''
return '->'.join(str(i) for i in self)
#note: this is NOT the class lab! see file linked.py.
def extend(self, iterable):
'''takes an iterable, and append all items in the iterable
to the end of the list self.'''
last = self.data
for i in iterable:
last.next = linkst(None, i)
last = last.next
self.data = last
def index(self, data):
'''TODO: return first index of data in the list self.
Raises ValueError if the value is not present.'''
#must not convert self to a tuple or any other containers
current, idx = self.next, 0
while current:
if current.data == data: return idx
current, idx = current.next, idx+1
raise ValueError(data)
于 2011-12-03T11:20:54.800 に答える
0
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
def insert(self, node):
if not self.next:
self.next = node
else:
self.next.insert(node)
def __str__(self):
if self.next:
return '%s -> %s' % (self.value, str(self.next))
else:
return ' %s ' % self.value
if __name__ == "__main__":
items = ['a', 'b', 'c', 'd', 'e']
ll = None
for item in items:
if ll:
next_ll = LinkedList(item)
ll.insert(next_ll)
else:
ll = LinkedList(item)
print('[ %s ]' % ll)
于 2013-07-25T05:49:11.463 に答える
-1
私の二重リンクリストは、初心者には理解できるかもしれません。C での DS に精通している場合、これは非常に読みやすいものです。
# LinkedList..
class node:
def __init__(self): ##Cluster of Nodes' properties
self.data=None
self.next=None
self.prev=None
class linkedList():
def __init__(self):
self.t = node() // for future use
self.cur_node = node() // current node
self.start=node()
def add(self,data): // appending the LL
self.new_node = node()
self.new_node.data=data
if self.cur_node.data is None:
self.start=self.new_node //For the 1st node only
self.cur_node.next=self.new_node
self.new_node.prev=self.cur_node
self.cur_node=self.new_node
def backward_display(self): //Displays LL backwards
self.t=self.cur_node
while self.t.data is not None:
print(self.t.data)
self.t=self.t.prev
def forward_display(self): //Displays LL Forward
self.t=self.start
while self.t.data is not None:
print(self.t.data)
self.t=self.t.next
if self.t.next is None:
print(self.t.data)
break
def main(self): //This is kind of the main
function in C
ch=0
while ch is not 4: //Switch-case in C
ch=int(input("Enter your choice:"))
if ch is 1:
data=int(input("Enter data to be added:"))
ll.add(data)
ll.main()
elif ch is 2:
ll.forward_display()
ll.main()
elif ch is 3:
ll.backward_display()
ll.main()
else:
print("Program ends!!")
return
ll=linkedList()
ll.main()
このコードにはさらに多くの単純化を追加できますが、未加工の実装の方が理解しやすいと思いました。
于 2017-10-15T14:06:44.880 に答える
-4
シンプルないいねリストを作成したい場合は、このコードを参照してください
l=[1,[2,[3,[4,[5,[6,[7,[8,[9,[10]]]]]]]]]]
このタラの実行を視覚化するには、http: //www.pythontutor.com/visualize.html#mode=edit にアクセスしてください
于 2014-10-31T09:47:20.570 に答える