私は、stackoverflow と Python 言語が初めてで、質問があります。Python で単方向リンク リストを実装する方法は知っていますが、二重リンク リストで問題が発生しています。具体的には、二重リンク リストの途中に挿入することです。これを行うためのコードを手伝ってくれる人はいますか? ありがとうございました
質問する
3994 次
1 に答える
5
私もPythonは初めてですが、お役に立てれば幸いです。私があなたの質問を正しく受け取った場合、次のような (古典的な) リンク リストの実装があるとします。
# Simple LinkedList class
class LinkedList:
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
# Just a string representation
def __str__(self):
if self.next:
return '%s %s' % (str(self.data), self.next.__str__())
else:
return '%s' % str(self.data)
リンクされたリストの端を知っていれば、端から端まで同時に反復することにより、要素を中央に簡単に挿入できます。イテレータが交差したら、要素を追加します。
# Insert to middle logic
def insertToMiddle(data, left, right):
# Iterate
while True:
# Test for intersection
if left.next is right:
node = LinkedList(data, left, right)
left.next = node
right.prev = node
return
elif left is right:
node = LinkedList(data, left.prev, right.next)
left.next = node
right.next.prev = node
return
# Next iteration
left = left.next
right = right.prev
# This doesn't actually execute for a right call
if not left or not right:
return
以下に、リンクされたリストの作成と、挿入前と挿入後のその表現を示します。
# Sample list creation
node1 = LinkedList(1)
node2 = LinkedList(2,node1)
node3 = LinkedList(3,node2)
node4 = LinkedList(4,node3)
node1.next = node2
node2.next = node3
node3.next = node4
# Test
print node1
insertToMiddle(5, node1, node4)
print node1
insertToMiddle(6, node1, node4)
print node1
insertToMiddle(7, node1, node4)
print node1
出力:
1 2 3 4 #initial
1 2 5 3 4 #inserted 5
1 2 5 6 3 4 #inserted 6, notice it's right to middle
1 2 5 7 6 3 4 #inserted 7
注意: リストに奇数の要素 (たとえば 2 3 4) がある場合、中央への挿入はどういうわけか定義されていないため、上記の関数は中央の右側 (2 3 elem 4) にすぐに追加します。
于 2012-11-12T23:54:16.863 に答える