Frage
Was ist der einfachste Weg, eine verkettete Liste in Python zu benutzen? In Schema wird eine verknüpfte Liste definiert einfach durch '(1 2 3 4 5)
. Python-Listen, [1, 2, 3, 4, 5]
und Tupel, (1, 2, 3, 4, 5)
, sind nicht in der Tat, verkettete Listen, und verkettete Listen haben einige netten Eigenschaften wie konstante Zeit Verkettung und separate Teile von ihnen verweisen zu können. Machen Sie sie unveränderlich und sie sind einfach mit! Arbeiten
Lösung
Hier finden Sie einige Listen-Funktionen basierend auf Martin v Löwis Vertretung :.
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")
Dabei gilt w = sys.stdout.write
Obwohl doppelt verkettete Listen berühmt in Raymond Hettinger verwendet werden bestellt Rezept gesetzt, einzeln verkettete Listen haben keinen praktischen Wert in Python.
Ich habe nie verwendet, um eine einzeln verknüpfte Liste in Python für jedes Problem außer Bildungs.
Thomas Watnedal vorgeschlagen eine gute pädagogische Ressource Wie 17 Wie ein Informatiker, Kapitel denken: Verknüpfte Listen :
Eine verkettete Liste ist entweder:
- die leere Liste, repräsentiert durch None oder
-
ein Knoten, der eine Ladung Objekt und einen Verweis auf eine verknüpfte Liste enthält.
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")
Andere Tipps
Für einige Bedürfnisse, ein deque auch nützlich sein können. Sie können Elemente an beiden Enden eines Deque bei O (1) Kosten hinzufügen und entfernen.
from collections import deque
d = deque([1,2,3,4])
print d
for x in d:
print x
print d.pop(), d
Ich schrieb dies den anderen Tag bis
#! /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()
Die akzeptierte Antwort ist ziemlich kompliziert. Hier ist eine Standardausführung:
L = LinkedList()
L.insert(1)
L.insert(1)
L.insert(2)
L.insert(4)
print L
L.clear()
print L
Es ist eine einfache LinkedList
Klasse basiert auf der einfachen C ++ Design und Kapitel 17: Verknüpfte Listen , wie von Thomas Watnedal empfohlen.
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__()
Immutable Listen werden am besten durch zwei-Tupel dargestellt, mit None NIL darstellt. Damit einfache Formulierung solcher Listen, können Sie diese Funktion verwenden:
def mklist(*args):
result = None
for element in reversed(args):
result = (element, result)
return result
mit solchen Listen arbeiten, würde ich eher die ganze Sammlung von LISP-Funktionen zur Verfügung stellen (das heißt erster, zweite, n-ten, usw.), als Methoden eingeführt werden.
Hier ist eine etwas komplexere Version einer Liste Klasse verbunden ist, mit einer ähnlichen Schnittstelle zu Pythons Sequenztypen (dh. Unterstützt die Indizierung, schneiden, Verkettung mit beliebigen Sequenzen usw.). Es sollte O (1) prepend haben, hat die Daten nicht kopiert werden, es sei denn es muss und kann ziemlich austauschbar mit Tupeln verwendet werden.
Es wird nicht als Raum und Zeit effizient wie Lisp cons Zellen sein, wie Python Klassen natürlich ein bisschen mehr Schwergewicht sind (Sie könnten die Dinge etwas mit „__slots__ = '_head','_tail'
“ verbessern die Speichernutzung zu reduzieren). Es wird jedoch die gewünschten großen O-Performance-Eigenschaften hat.
Beispiel für die Verwendung:
>>> 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])
Umsetzung:
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
llist - verlinkte Liste Datentypen für Python
llist Modul implementiert Liste Datenstrukturen verknüpft. Es unterstützt eine doppelt verknüpfte Liste, das heißt dllist
und eine einfach Datenstruktur sllist
verknüpft.
dllist Objekte
Dieses Objekt stellt eine doppelt verknüpfte Listendatenstruktur.
first
Erstes dllistnode
Objekt in der Liste. None
wenn Liste ist leer.
last
Zuletzt dllistnode
Objekt in der Liste. Keine, wenn die Liste leer ist.
dllist Objekte auch folgende Methoden unterstützen:
append(x)
x
auf der rechten Seite der Liste hinzufügen und eingefügt dllistnode
zurück.
appendleft(x)
x
auf der linken Seite der Liste hinzufügen und eingefügt dllistnode
zurück.
appendright(x)
x
auf der rechten Seite der Liste hinzufügen und eingefügt dllistnode
zurück.
clear()
Entfernen alle Knoten aus der Liste.
extend(iterable)
Fügen Sie Elemente aus iterable
auf der rechten Seite der Liste.
extendleft(iterable)
Fügen Sie Elemente aus iterable
auf der linken Seite der Liste.
extendright(iterable)
Fügen Sie Elemente aus iterable
auf der rechten Seite der Liste.
insert(x[, before])
In x
auf der rechten Seite der Liste, wenn before
nicht angegeben, oder x
auf der linken Seite des dllistnode before
einzufügen. Return eingefügt dllistnode
.
nodeat(index)
Return Knoten (vom Typ dllistnode
) bei index
.
pop()
entfernen und den Wert eines Elements von der rechten Seite der Liste zurück.
popleft()
entfernen und den Wert eines Elements von der linken Seite der Liste zurück.
popright()
entfernen und den Wert eines Elements von der rechten Seite der Liste zurück
remove(node)
Entfernen node
aus der Liste aus und senden Sie das Element, das in ihm gespeichert wurde.
dllistnode
Objekte
Klasse llist.dllistnode([value])
Gibt einen neuen doppelt verknüpften Liste Knoten initialisiert (optional) mit value
.
dllistnode
Objekte bieten folgende Attribute:
next
Als nächstes Knoten in der Liste. Dieses Attribut ist schreibgeschützt.
prev
Zurück Knoten in der Liste. Dieses Attribut ist schreibgeschützt.
value
Wert in diesem Knoten gespeichert. aus dieser Referenz Zusammengestellt
sllist
Klasse llist.sllist([iterable])
Gibt eine neue einzeln verknüpfte Liste mit Elementen aus iterable
initialisiert. Wenn iterable nicht angegeben ist, der neue sllist
leer ist.
Ein ähnlicher Satz von Attributen und Operationen sind für dieses Objekt definiert sllist
. für weitere Informationen zu dieser Referenz.
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def setData(self, data):
self.data = data
return self.data
def setNext(self, next):
self.next = next
def getNext(self):
return self.next
def hasNext(self):
return self.next != None
class singleLinkList(object):
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def insertAtBeginning(self, data):
newNode = Node()
newNode.setData(data)
if self.listLength() == 0:
self.head = newNode
else:
newNode.setNext(self.head)
self.head = newNode
def insertAtEnd(self, data):
newNode = Node()
newNode.setData(data)
current = self.head
while current.getNext() != None:
current = current.getNext()
current.setNext(newNode)
def listLength(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
def print_llist(self):
current = self.head
print("List Start.")
while current != None:
print(current.getData())
current = current.getNext()
print("List End.")
if __name__ == '__main__':
ll = singleLinkList()
ll.insertAtBeginning(55)
ll.insertAtEnd(56)
ll.print_llist()
print(ll.listLength())
I basiert diese zusätzliche Funktion auf 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
Die Methode hat er fügt den neuen Knoten am Anfang, während ich viele Implementierungen gesehen habe, die in der Regel einen neuen Knoten am Ende hinzufügen, aber was auch immer, es macht Spaß zu tun.
Im Folgenden ist das, was ich kam mit. Es ist similer zum Riccardo C. Der , in diesem Thread, außer es die Zahlen, um druckt statt umgekehrt. Ich habe auch die LinkedList ein Python-Iterator, um das Objekt der Liste aus wie bei einem normalen Python-Liste.
druckenclass 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
"""
Ich habe gerade dieser als Spaß Spielzeug. Es sollte so lange unveränderlich sein, da Sie nicht über die Unterstrich-Präfix Methoden berühren, und es implementiert eine Reihe von Python Magie wie die Indizierung und len
.
Wenn unveränderlich verknüpfte Listen verwenden, sollten Sie direkt Python Tupel verwenden.
ls = (1, 2, 3, 4, 5)
def first(ls): return ls[0]
def rest(ls): return ls[1:]
Es ist wirklich, dass Leichtigkeit, und Sie erhalten die zusätzlichen funcitons wie len zu halten (ls), x in ls, etc.
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)
Ich habe eine Python 2.x und 3.x setzen einfach verknüpften Liste Klasse unter https: //pypi.python.org/pypi/linked_list_mod/
Es ist mit CPython getestet 2.7, 3.4 CPython, PyPy 2.3.1, 2.3.1 Pypy3 und Jython 2.7b2, und kommt mit einer netten automatisierten Test-Suite.
Es enthält auch LIFO und FIFO-Klassen.
Sie sind aber nicht unveränderlich.
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
verlinkte Liste Klasse
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
Verwendung
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(), '-|----> ',
Output
| 55 | 25 -|----> | 25 | 10 -|----> | 10 | --> None
Hier ist meine einfache Implementierung:
class Node:
def __init__(self):
self.data = None
self.next = None
def __str__(self):
return "Data %s: Next -> %s"%(self.data, self.next)
class LinkedList:
def __init__(self):
self.head = Node()
self.curNode = self.head
def insertNode(self, data):
node = Node()
node.data = data
node.next = None
if self.head.data == None:
self.head = node
self.curNode = node
else:
self.curNode.next = node
self.curNode = node
def printList(self):
print self.head
l = LinkedList()
l.insertNode(1)
l.insertNode(2)
l.insertNode(34)
Ausgabe:
Data 1: Next -> Data 2: Next -> Data 34: Next -> Data 4: Next -> None
Hier ist meine Lösung:
Die Umsetzung
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def get_data(self):
return self.data
def set_data(self, data):
self.data = data
def get_next(self):
return self.next
def set_next(self, node):
self.next = node
# ------------------------ Link List class ------------------------------- #
class LinkList:
def __init__(self):
self.head = None
def is_empty(self):
return self.head == None
def traversal(self, data=None):
node = self.head
index = 0
found = False
while node is not None and not found:
if node.get_data() == data:
found = True
else:
node = node.get_next()
index += 1
return (node, index)
def size(self):
_, count = self.traversal(None)
return count
def search(self, data):
node, _ = self.traversal(data)
return node
def add(self, data):
node = Node(data)
node.set_next(self.head)
self.head = node
def remove(self, data):
previous_node = None
current_node = self.head
found = False
while current_node is not None and not found:
if current_node.get_data() == data:
found = True
if previous_node:
previous_node.set_next(current_node.get_next())
else:
self.head = current_node
else:
previous_node = current_node
current_node = current_node.get_next()
return found
Verwendung
link_list = LinkList()
link_list.add(10)
link_list.add(20)
link_list.add(30)
link_list.add(40)
link_list.add(50)
link_list.size()
link_list.search(30)
link_list.remove(20)
Original Implementation Idee
Ich denke, die Umsetzung unter füllt die Rechnung ganz elegant.
'''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)
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)
Zunächst einmal, ich nehme an, Sie verkettete Listen wollen. In der Praxis kann man collections.deque
verwenden, dessen Strom CPython Implementierung ist eine doppelt verknüpfte Liste von Blöcken (jeder Block enthält ein Array von 62 Ladungsgegenständen). Es subsumiert Liste der Funktionalität verknüpft. Sie können auch für eine C-Erweiterung namens llist
auf pypi suchen. Wenn Sie eine reine Python und einfach zu folgen Umsetzung der verknüpften Liste ADT möchten, können Sie einen Blick auf meine folgende minimale Implementierung nehmen.
class Node (object):
""" Node for a linked list. """
def __init__ (self, value, next=None):
self.value = value
self.next = next
class LinkedList (object):
""" Linked list ADT implementation using class.
A linked list is a wrapper of a head pointer
that references either None, or a node that contains
a reference to a linked list.
"""
def __init__ (self, iterable=()):
self.head = None
for x in iterable:
self.head = Node(x, self.head)
def __iter__ (self):
p = self.head
while p is not None:
yield p.value
p = p.next
def prepend (self, x): # 'appendleft'
self.head = Node(x, self.head)
def reverse (self):
""" In-place reversal. """
p = self.head
self.head = None
while p is not None:
p0, p = p, p.next
p0.next = self.head
self.head = p0
if __name__ == '__main__':
ll = LinkedList([6,5,4])
ll.prepend(3); ll.prepend(2)
print list(ll)
ll.reverse()
print list(ll)
Beispiel für eine doppelt verkettete Liste (speichern als linkedlist.py):
class node:
def __init__(self, before=None, cargo=None, next=None):
self._previous = before
self._cargo = cargo
self._next = next
def __str__(self):
return str(self._cargo) or None
class linkedList:
def __init__(self):
self._head = None
self._length = 0
def add(self, cargo):
n = node(None, cargo, self._head)
if self._head:
self._head._previous = n
self._head = n
self._length += 1
def search(self,cargo):
node = self._head
while (node and node._cargo != cargo):
node = node._next
return node
def delete(self,cargo):
node = self.search(cargo)
if node:
prev = node._previous
nx = node._next
if prev:
prev._next = node._next
else:
self._head = nx
nx._previous = None
if nx:
nx._previous = prev
else:
prev._next = None
self._length -= 1
def __str__(self):
print 'Size of linked list: ',self._length
node = self._head
while node:
print node
node = node._next
Testing (speichern als test.py):
from linkedlist import node, linkedList
def test():
print 'Testing Linked List'
l = linkedList()
l.add(10)
l.add(20)
l.add(30)
l.add(40)
l.add(50)
l.add(60)
print 'Linked List after insert nodes:'
l.__str__()
print 'Search some value, 30:'
node = l.search(30)
print node
print 'Delete some value, 30:'
node = l.delete(30)
l.__str__()
print 'Delete first element, 60:'
node = l.delete(60)
l.__str__()
print 'Delete last element, 10:'
node = l.delete(10)
l.__str__()
if __name__ == "__main__":
test()
Output :
Testing Linked List
Linked List after insert nodes:
Size of linked list: 6
60
50
40
30
20
10
Search some value, 30:
30
Delete some value, 30:
Size of linked list: 5
60
50
40
20
10
Delete first element, 60:
Size of linked list: 4
50
40
20
10
Delete last element, 10:
Size of linked list: 3
50
40
20
Meine 2 Cent
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def __str__(self):
return str(self.value)
class LinkedList:
def __init__(self):
self.first = None
self.last = None
def add(self, x):
current = Node(x, None)
try:
self.last.next = current
except AttributeError:
self.first = current
self.last = current
else:
self.last = current
def print_list(self):
node = self.first
while node:
print node.value
node = node.next
ll = LinkedList()
ll.add("1st")
ll.add("2nd")
ll.add("3rd")
ll.add("4th")
ll.add("5th")
ll.print_list()
# Result:
# 1st
# 2nd
# 3rd
# 4th
# 5th
enter code here
enter code here
class node:
def __init__(self):
self.data = None
self.next = None
class linked_list:
def __init__(self):
self.cur_node = None
self.head = None
def add_node(self,data):
new_node = node()
if self.head == None:
self.head = new_node
self.cur_node = new_node
new_node.data = data
new_node.next = None
self.cur_node.next = new_node
self.cur_node = new_node
def list_print(self):
node = self.head
while node:
print (node.data)
node = node.next
def delete(self):
node = self.head
next_node = node.next
del(node)
self.head = next_node
a = linked_list()
a.add_node(1)
a.add_node(2)
a.add_node(3)
a.add_node(4)
a.delete()
a.list_print()
meine Doppel verlinkte Liste könnte noobies verständlich sein. Wenn Sie mit DS in C vertraut sind, ist dies gut lesbar.
# 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()
Obwohl viele weiteren Vereinfachungen können zu diesem Code hinzugefügt werden, dachte ich eine rohe Umsetzung würde ich mehr Greifergut.
Wenn Sie wollen einfach nur eine einfache gemocht Liste erstellen Sie dann diesen Code beziehen
l = [1, [2, [3 [4 [5, [6, [7, [8, [9, [10]]]]]]]]]]
für visualize Ausführung für diesen cod Besuch http://www.pythontutor.com/visualize .html # mode = bearbeiten