Quelle est la façon la plus simple d'utiliser une liste chaînée en python? Dans le schéma, une liste chaînée est définie simplement par '(1 2 3 4 5)
. Les listes, [1, 2, 3, 4, 5]
et les tuples de Python (1, 2, 3, 4, 5)
ne sont pas, en fait, des listes liées, et les listes liées ont quelques propriétés intéressantes telles que la concaténation à temps constant et la possibilité d'en référencer des parties distinctes. Rendez-les immuables et ils sont vraiment faciles à utiliser!
python
linked-list
Claudiu
la source
la source
Réponses:
Voici quelques fonctions de liste basées sur la représentation de Martin contre 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")
où
w = sys.stdout.write
Bien que les listes à double chaînage soient utilisées dans la recette d'ensemble ordonnée de Raymond Hettinger , les listes à liaison simple n'ont aucune valeur pratique en Python.
Je n'ai jamais utilisé une seule liste chaînée en Python pour aucun problème sauf éducatif.
Thomas Watnedal a suggéré une bonne ressource pédagogique Comment penser comme un informaticien, Chapitre 17: Listes liées :
Une liste chaînée est soit:
un nœud qui contient un objet cargo et une référence à une liste liée.
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")
la source
Pour certains besoins, un deque peut également être utile. Vous pouvez ajouter et supprimer des éléments aux deux extrémités d'un deque au coût O (1).
from collections import deque d = deque([1,2,3,4]) print d for x in d: print x print d.pop(), d
la source
deque
qu'il s'agisse d'un type de données utile, ce n'est pas une liste chaînée (bien qu'elle soit implémentée en utilisant une liste doublement liée au niveau C). Cela répond donc à la question "qu'utiliseriez-vous à la place des listes chaînées en Python?" et dans ce cas, la première réponse devrait être (pour certains besoins) une liste Python ordinaire (ce n'est pas non plus une liste chaînée).linked_list[n]
) car ce serait O (n). Les déqueues l'autorisent et l'exécutent dans O (1). Cependant, les listes chaînées, étant donné un itérateur dans la liste, peuvent permettre l'insertion et la suppression de O (1), alors que deques ne le peut pas (c'est O (n), comme un vecteur). (Sauf au début et à la fin, où les deques et les listes chaînées sont tous deux O (1). (Bien que le deque soit probablement amorti O (1). La liste chaînée ne l'est pas.)O(n)
). Si "presque tous les moyens" permet d'ignorer la différence de gros O alors votre déclaration n'a pas de sens car nous pourrions utiliser une liste intégrée Python comme un deque si ce n'était pas pour pop (0), insert (0, v) big O garantit .J'ai écrit ça l'autre jour
#! /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()
la source
list_print()
.La réponse acceptée est plutôt compliquée. Voici une conception plus standard:
L = LinkedList() L.insert(1) L.insert(1) L.insert(2) L.insert(4) print L L.clear() print L
C'est une
LinkedList
classe simple basée sur la conception C ++ simple et le chapitre 17: Listes liées , comme recommandé par 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__()
la source
X is None
c'est préférable==
. stackoverflow.com/a/2988117/1740227insert
n'est-il pas un cas particulier du troisième, de sorte que vous puissiez entièrement supprimer laelif
clause?Les listes immuables sont mieux représentées par deux tuples, aucun représentant NIL. Pour permettre la formulation simple de telles listes, vous pouvez utiliser cette fonction:
def mklist(*args): result = None for element in reversed(args): result = (element, result) return result
Pour travailler avec de telles listes, je préfère fournir toute la collection de fonctions LISP (c'est-à-dire premier, deuxième, nième, etc.), plutôt que d'introduire des méthodes.
la source
Voici une version légèrement plus complexe d'une classe de liste chaînée, avec une interface similaire aux types de séquence de python (c'est-à-dire prend en charge l'indexation, le découpage, la concaténation avec des séquences arbitraires, etc.). Il devrait avoir O (1) en préfixe, ne copie pas les données sauf si nécessaire et peut être utilisé de manière interchangeable avec les tuples.
Ce ne sera pas aussi efficace en termes d'espace ou de temps que les cellules lisp contre, car les classes python sont évidemment un peu plus lourdes (vous pouvez améliorer légèrement les choses avec "
__slots__ = '_head','_tail'
" pour réduire l'utilisation de la mémoire). Il aura cependant les caractéristiques de performances souhaitées en gros O.Exemple d'utilisation:
>>> 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])
La mise en oeuvre:
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
la source
llist - types de données de listes liées pour Python
Le module llist implémente des structures de données de listes liées. Il prend en charge une liste doublement liée, c'est
dllist
-à- dire et une structure de données liée individuellementsllist
.objets dllist
Cet objet représente une structure de données de liste doublement liée.
first
Premier
dllistnode
objet de la liste.None
si la liste est vide.last
Dernier
dllistnode
objet de la liste. Aucun si la liste est vide.Les objets dllist prennent également en charge les méthodes suivantes:
append(x)
Ajouter
x
à droite de la liste et retourner insérédllistnode
.appendleft(x)
Ajouter
x
au côté gauche de la liste et retourner insérédllistnode
.appendright(x)
Ajouter
x
à droite de la liste et retourner insérédllistnode
.clear()
Supprimez tous les nœuds de la liste.
extend(iterable)
Ajoutez des éléments du
iterable
côté droit de la liste.extendleft(iterable)
Ajoutez des éléments du
iterable
côté gauche de la liste.extendright(iterable)
Ajoutez des éléments du
iterable
côté droit de la liste.insert(x[, before])
Ajouter
x
à droite de la liste sibefore
n'est pas spécifié, ou insérerx
à gauche dedllistnode before
. Retour insérédllistnode
.nodeat(index)
Nœud de retour (de type
dllistnode
) àindex
.pop()
Supprimez et renvoyez la valeur d'un élément du côté droit de la liste.
popleft()
Supprimez et renvoyez la valeur d'un élément du côté gauche de la liste.
popright()
Supprimer et renvoyer la valeur d'un élément du côté droit de la liste
remove(node)
Supprimer
node
de la liste et renvoyer l'élément qui y était stocké.dllistnode
objetsclasse
llist.dllistnode([value])
Renvoie un nouveau nœud de liste doublement lié, initialisé (éventuellement) avec
value
.dllistnode
les objets fournissent les attributs suivants:next
Nœud suivant dans la liste. Cet attribut est en lecture seule.
prev
Noeud précédent dans la liste. Cet attribut est en lecture seule.
value
Valeur stockée dans ce nœud. Compilé à partir de cette référence
sllist
class
llist.sllist([iterable])
Renvoie une nouvelle liste liée individuellement initialisée avec des éléments deiterable
. Si iterable n'est pas spécifié, le nouveausllist
est vide.Un ensemble similaire d'attributs et d'opérations est défini pour cet
sllist
objet. Consultez cette référence pour plus d'informations.la source
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())
la source
J'ai basé cette fonction supplémentaire sur 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
La méthode qu'il a ajoute le nouveau nœud au début alors que j'ai vu beaucoup d'implémentations qui ajoutent généralement un nouveau nœud à la fin mais quoi qu'il en soit, c'est amusant à faire.
la source
Voici ce que j'ai trouvé. C'est similaire à celui de Riccardo C. , dans ce fil, sauf qu'il imprime les nombres dans l'ordre au lieu de l'inverse. J'ai également fait de l'objet LinkedList un itérateur Python afin d'imprimer la liste comme vous le feriez pour une liste Python normale.
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 """
la source
Je viens de faire ça comme un jouet amusant. Il doit être immuable tant que vous ne touchez pas aux méthodes avec préfixe de soulignement et implémente un tas de magie Python comme l'indexation et
len
.la source
Lorsque vous utilisez des listes liées immuables, pensez à utiliser directement le tuple de Python.
ls = (1, 2, 3, 4, 5) def first(ls): return ls[0] def rest(ls): return ls[1:]
C'est vraiment cette facilité, et vous pouvez garder les fonctions supplémentaires comme len (ls), x dans ls, etc.
la source
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)
la source
J'ai mis une classe de liste Python 2.x et 3.x à un seul lien sur https://pypi.python.org/pypi/linked_list_mod/
Il est testé avec CPython 2.7, CPython 3.4, Pypy 2.3.1, Pypy3 2.3.1 et Jython 2.7b2, et est livré avec une belle suite de tests automatisés.
Il comprend également des classes LIFO et FIFO.
Ils ne sont cependant pas immuables.
la source
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
la source
Classe de liste liée
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
Usage
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(), '-|----> ',
Production
| 55 | 25 -|----> | 25 | 10 -|----> | 10 | --> None
la source
Voici ma mise en œuvre simple:
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)
Production:
Data 1: Next -> Data 2: Next -> Data 34: Next -> Data 4: Next -> None
la source
Voici ma solution:
la mise en oeuvre
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
Usage
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)
Idée de mise en œuvre originale
la source
Je pense que la mise en œuvre ci-dessous remplit le projet de loi avec grâce.
'''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)
la source
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)
la source
Tout d'abord, je suppose que vous voulez des listes chaînées. En pratique, vous pouvez utiliser
collections.deque
, dont l'implémentation CPython actuelle est une liste de blocs doublement liés (chaque bloc contient un tableau de 62 objets cargo). Il englobe la fonctionnalité de la liste liée. Vous pouvez également rechercher une extension C appeléellist
sur pypi. Si vous voulez une implémentation pure-Python et facile à suivre de la liste chaînée ADT, vous pouvez jeter un œil à mon implémentation minimale suivante.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)
la source
Exemple de liste doublement liée (enregistrer sous 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
Test (enregistrer sous 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()
Sortie :
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
la source
J'ai également écrit une liste liée unique basée sur un didacticiel, qui contient les deux classes de base Node et Linked List, et quelques méthodes supplémentaires pour l'insertion, la suppression, l'inversion, le tri, etc.
Ce n'est ni le meilleur ni le plus simple, mais ça marche bien.
""" 🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏 Single Linked List (SLL): A simple object-oriented implementation of Single Linked List (SLL) with some associated methods, such as create list, count nodes, delete nodes, and such. 🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏🍎🍏 """ class Node: """ Instantiates a node """ def __init__(self, value): """ Node class constructor which sets the value and link of the node """ self.info = value self.link = None class SingleLinkedList: """ Instantiates the SLL class """ def __init__(self): """ SLL class constructor which sets the value and link of the node """ self.start = None def create_single_linked_list(self): """ Reads values from stdin and appends them to this list and creates a SLL with integer nodes """ try: number_of_nodes = int(input("👉 Enter a positive integer between 1-50 for the number of nodes you wish to have in the list: ")) if number_of_nodes <= 0 or number_of_nodes > 51: print("💛 The number of nodes though must be an integer between 1 to 50!") self.create_single_linked_list() except Exception as e: print("💛 Error: ", e) self.create_single_linked_list() try: for _ in range(number_of_nodes): try: data = int(input("👉 Enter an integer for the node to be inserted: ")) self.insert_node_at_end(data) except Exception as e: print("💛 Error: ", e) except Exception as e: print("💛 Error: ", e) def count_sll_nodes(self): """ Counts the nodes of the linked list """ try: p = self.start n = 0 while p is not None: n += 1 p = p.link if n >= 1: print(f"💚 The number of nodes in the linked list is {n}") else: print(f"💛 The SLL does not have a node!") except Exception as e: print("💛 Error: ", e) def search_sll_nodes(self, x): """ Searches the x integer in the linked list """ try: position = 1 p = self.start while p is not None: if p.info == x: print(f"💚 YAAAY! We found {x} at position {position}") return True #Increment the position position += 1 #Assign the next node to the current node p = p.link else: print(f"💔 Sorry! We couldn't find {x} at any position. Maybe, you might want to use option 9 and try again later!") return False except Exception as e: print("💛 Error: ", e) def display_sll(self): """ Displays the list """ try: if self.start is None: print("💛 Single linked list is empty!") return display_sll = "💚 Single linked list nodes are: " p = self.start while p is not None: display_sll += str(p.info) + "\t" p = p.link print(display_sll) except Exception as e: print("💛 Error: ", e) def insert_node_in_beginning(self, data): """ Inserts an integer in the beginning of the linked list """ try: temp = Node(data) temp.link = self.start self.start = temp except Exception as e: print("💛 Error: ", e) def insert_node_at_end(self, data): """ Inserts an integer at the end of the linked list """ try: temp = Node(data) if self.start is None: self.start = temp return p = self.start while p.link is not None: p = p.link p.link = temp except Exception as e: print("💛 Error: ", e) def insert_node_after_another(self, data, x): """ Inserts an integer after the x node """ try: p = self.start while p is not None: if p.info == x: break p = p.link if p is None: print(f"💔 Sorry! {x} is not in the list.") else: temp = Node(data) temp.link = p.link p.link = temp except Exception as e: print("💛 Error: ", e) def insert_node_before_another(self, data, x): """ Inserts an integer before the x node """ try: # If list is empty if self.start is None: print("💔 Sorry! The list is empty.") return # If x is the first node, and new node should be inserted before the first node if x == self.start.info: temp = Node(data) temp.link = p.link p.link = temp # Finding the reference to the prior node containing x p = self.start while p.link is not None: if p.link.info == x: break p = p.link if p.link is not None: print(f"💔 Sorry! {x} is not in the list.") else: temp = Node(data) temp.link = p.link p.link = temp except Exception as e: print("💛 Error: ", e) def insert_node_at_position(self, data, k): """ Inserts an integer in k position of the linked list """ try: # if we wish to insert at the first node if k == 1: temp = Node(data) temp.link = self.start self.start = temp return p = self.start i = 1 while i < k-1 and p is not None: p = p.link i += 1 if p is None: print(f"💛 The max position is {i}") else: temp = Node(data) temp.link = self.start self.start = temp except Exception as e: print("💛 Error: ", e) def delete_a_node(self, x): """ Deletes a node of a linked list """ try: # If list is empty if self.start is None: print("💔 Sorry! The list is empty.") return # If there is only one node if self.start.info == x: self.start = self.start.link # If more than one node exists p = self.start while p.link is not None: if p.link.info == x: break p = p.link if p.link is None: print(f"💔 Sorry! {x} is not in the list.") else: p.link = p.link.link except Exception as e: print("💛 Error: ", e) def delete_sll_first_node(self): """ Deletes the first node of a linked list """ try: if self.start is None: return self.start = self.start.link except Exception as e: print("💛 Error: ", e) def delete_sll_last_node(self): """ Deletes the last node of a linked list """ try: # If the list is empty if self.start is None: return # If there is only one node if self.start.link is None: self.start = None return # If there is more than one node p = self.start # Increment until we find the node prior to the last node while p.link.link is not None: p = p.link p.link = None except Exception as e: print("💛 Error: ", e) def reverse_sll(self): """ Reverses the linked list """ try: prev = None p = self.start while p is not None: next = p.link p.link = prev prev = p p = next self.start = prev except Exception as e: print("💛 Error: ", e) def bubble_sort_sll_nodes_data(self): """ Bubble sorts the linked list on integer values """ try: # If the list is empty or there is only one node if self.start is None or self.start.link is None: print("💛 The list has no or only one node and sorting is not required.") end = None while end != self.start.link: p = self.start while p.link != end: q = p.link if p.info > q.info: p.info, q.info = q.info, p.info p = p.link end = p except Exception as e: print("💛 Error: ", e) def bubble_sort_sll(self): """ Bubble sorts the linked list """ try: # If the list is empty or there is only one node if self.start is None or self.start.link is None: print("💛 The list has no or only one node and sorting is not required.") end = None while end != self.start.link: r = p = self.start while p.link != end: q = p.link if p.info > q.info: p.link = q.link q.link = p if p != self.start: r.link = q.link else: self.start = q p, q = q, p r = p p = p.link end = p except Exception as e: print("💛 Error: ", e) def sll_has_cycle(self): """ Tests the list for cycles using Tortoise and Hare Algorithm (Floyd's cycle detection algorithm) """ try: if self.find_sll_cycle() is None: return False else: return True except Exception as e: print("💛 Error: ", e) def find_sll_cycle(self): """ Finds cycles in the list, if any """ try: # If there is one node or none, there is no cycle if self.start is None or self.start.link is None: return None # Otherwise, slowR = self.start fastR = self.start while slowR is not None and fastR is not None: slowR = slowR.link fastR = fastR.link.link if slowR == fastR: return slowR return None except Exception as e: print("💛 Error: ", e) def remove_cycle_from_sll(self): """ Removes the cycles """ try: c = self.find_sll_cycle() # If there is no cycle if c is None: return print(f"💛 There is a cycle at node: ", c.info) p = c q = c len_cycles = 0 while True: len_cycles += 1 q = q.link if p == q: break print(f"💛 The cycle length is {len_cycles}") len_rem_list = 0 p = self.start while p != q: len_rem_list += 1 p = p.link q = q.link print(f"💛 The number of nodes not included in the cycle is {len_rem_list}") length_list = len_rem_list + len_cycles print(f"💛 The SLL length is {length_list}") # This for loop goes to the end of the SLL, and set the last node to None and the cycle is removed. p = self.start for _ in range(length_list-1): p = p.link p.link = None except Exception as e: print("💛 Error: ", e) def insert_cycle_in_sll(self, x): """ Inserts a cycle at a node that contains x """ try: if self.start is None: return False p = self.start px = None prev = None while p is not None: if p.info == x: px = p prev = p p = p.link if px is not None: prev.link = px else: print(f"💔 Sorry! {x} is not in the list.") except Exception as e: print("💛 Error: ", e) def merge_using_new_list(self, list2): """ Merges two already sorted SLLs by creating new lists """ merge_list = SingleLinkedList() merge_list.start = self._merge_using_new_list(self.start, list2.start) return merge_list def _merge_using_new_list(self, p1, p2): """ Private method of merge_using_new_list """ if p1.info <= p2.info: Start_merge = Node(p1.info) p1 = p1.link else: Start_merge = Node(p2.info) p2 = p2.link pM = Start_merge while p1 is not None and p2 is not None: if p1.info <= p2.info: pM.link = Node(p1.info) p1 = p1.link else: pM.link = Node(p2.info) p2 = p2.link pM = pM.link #If the second list is finished, yet the first list has some nodes while p1 is not None: pM.link = Node(p1.info) p1 = p1.link pM = pM.link #If the second list is finished, yet the first list has some nodes while p2 is not None: pM.link = Node(p2.info) p2 = p2.link pM = pM.link return Start_merge def merge_inplace(self, list2): """ Merges two already sorted SLLs in place in O(1) of space """ merge_list = SingleLinkedList() merge_list.start = self._merge_inplace(self.start, list2.start) return merge_list def _merge_inplace(self, p1, p2): """ Merges two already sorted SLLs in place in O(1) of space """ if p1.info <= p2.info: Start_merge = p1 p1 = p1.link else: Start_merge = p2 p2 = p2.link pM = Start_merge while p1 is not None and p2 is not None: if p1.info <= p2.info: pM.link = p1 pM = pM.link p1 = p1.link else: pM.link = p2 pM = pM.link p2 = p2.link if p1 is None: pM.link = p2 else: pM.link = p1 return Start_merge def merge_sort_sll(self): """ Sorts the linked list using merge sort algorithm """ self.start = self._merge_sort_recursive(self.start) def _merge_sort_recursive(self, list_start): """ Recursively calls the merge sort algorithm for two divided lists """ # If the list is empty or has only one node if list_start is None or list_start.link is None: return list_start # If the list has two nodes or more start_one = list_start start_two = self._divide_list(self_start) start_one = self._merge_sort_recursive(start_one) start_two = self._merge_sort_recursive(start_two) start_merge = self._merge_inplace(start_one, start_two) return start_merge def _divide_list(self, p): """ Divides the linked list into two almost equally sized lists """ # Refers to the third nodes of the list q = p.link.link while q is not None and p is not None: # Increments p one node at the time p = p.link # Increments q two nodes at the time q = q.link.link start_two = p.link p.link = None return start_two def concat_second_list_to_sll(self, list2): """ Concatenates another SLL to an existing SLL """ # If the second SLL has no node if list2.start is None: return # If the original SLL has no node if self.start is None: self.start = list2.start return # Otherwise traverse the original SLL p = self.start while p.link is not None: p = p.link # Link the last node to the first node of the second SLL p.link = list2.start def test_merge_using_new_list_and_inplace(self): """ """ LIST_ONE = SingleLinkedList() LIST_TWO = SingleLinkedList() LIST_ONE.create_single_linked_list() LIST_TWO.create_single_linked_list() print("1️⃣ The unsorted first list is: ") LIST_ONE.display_sll() print("2️⃣ The unsorted second list is: ") LIST_TWO.display_sll() LIST_ONE.bubble_sort_sll_nodes_data() LIST_TWO.bubble_sort_sll_nodes_data() print("1️⃣ The sorted first list is: ") LIST_ONE.display_sll() print("2️⃣ The sorted second list is: ") LIST_TWO.display_sll() LIST_THREE = LIST_ONE.merge_using_new_list(LIST_TWO) print("The merged list by creating a new list is: ") LIST_THREE.display_sll() LIST_FOUR = LIST_ONE.merge_inplace(LIST_TWO) print("The in-place merged list is: ") LIST_FOUR.display_sll() def test_all_methods(self): """ Tests all methods of the SLL class """ OPTIONS_HELP = """ 📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗 Select a method from 1-19: 🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒🍒 ℹ️ (1) 👉 Create a single liked list (SLL). ℹ️ (2) 👉 Display the SLL. ℹ️ (3) 👉 Count the nodes of SLL. ℹ️ (4) 👉 Search the SLL. ℹ️ (5) 👉 Insert a node at the beginning of the SLL. ℹ️ (6) 👉 Insert a node at the end of the SLL. ℹ️ (7) 👉 Insert a node after a specified node of the SLL. ℹ️ (8) 👉 Insert a node before a specified node of the SLL. ℹ️ (9) 👉 Delete the first node of SLL. ℹ️ (10) 👉 Delete the last node of the SLL. ℹ️ (11) 👉 Delete a node you wish to remove. ℹ️ (12) 👉 Reverse the SLL. ℹ️ (13) 👉 Bubble sort the SLL by only exchanging the integer values. ℹ️ (14) 👉 Bubble sort the SLL by exchanging links. ℹ️ (15) 👉 Merge sort the SLL. ℹ️ (16) 👉 Insert a cycle in the SLL. ℹ️ (17) 👉 Detect if the SLL has a cycle. ℹ️ (18) 👉 Remove cycle in the SLL. ℹ️ (19) 👉 Test merging two bubble-sorted SLLs. ℹ️ (20) 👉 Concatenate a second list to the SLL. ℹ️ (21) 👉 Exit. 📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗📗 """ self.create_single_linked_list() while True: print(OPTIONS_HELP) UI_OPTION = int(input("👉 Enter an integer for the method you wish to run using the above help: ")) if UI_OPTION == 1: data = int(input("👉 Enter an integer to be inserted at the end of the list: ")) x = int(input("👉 Enter an integer to be inserted after that: ")) self.insert_node_after_another(data, x) elif UI_OPTION == 2: self.display_sll() elif UI_OPTION == 3: self.count_sll_nodes() elif UI_OPTION == 4: data = int(input("👉 Enter an integer to be searched: ")) self.search_sll_nodes(data) elif UI_OPTION == 5: data = int(input("👉 Enter an integer to be inserted at the beginning: ")) self.insert_node_in_beginning(data) elif UI_OPTION == 6: data = int(input("👉 Enter an integer to be inserted at the end: ")) self.insert_node_at_end(data) elif UI_OPTION == 7: data = int(input("👉 Enter an integer to be inserted: ")) x = int(input("👉 Enter an integer to be inserted before that: ")) self.insert_node_before_another(data, x) elif UI_OPTION == 8: data = int(input("👉 Enter an integer for the node to be inserted: ")) k = int(input("👉 Enter an integer for the position at which you wish to insert the node: ")) self.insert_node_before_another(data, k) elif UI_OPTION == 9: self.delete_sll_first_node() elif UI_OPTION == 10: self.delete_sll_last_node() elif UI_OPTION == 11: data = int(input("👉 Enter an integer for the node you wish to remove: ")) self.delete_a_node(data) elif UI_OPTION == 12: self.reverse_sll() elif UI_OPTION == 13: self.bubble_sort_sll_nodes_data() elif UI_OPTION == 14: self.bubble_sort_sll() elif UI_OPTION == 15: self.merge_sort_sll() elif UI_OPTION == 16: data = int(input("👉 Enter an integer at which a cycle has to be formed: ")) self.insert_cycle_in_sll(data) elif UI_OPTION == 17: if self.sll_has_cycle(): print("💛 The linked list has a cycle. ") else: print("💚 YAAAY! The linked list does not have a cycle. ") elif UI_OPTION == 18: self.remove_cycle_from_sll() elif UI_OPTION == 19: self.test_merge_using_new_list_and_inplace() elif UI_OPTION == 20: list2 = self.create_single_linked_list() self.concat_second_list_to_sll(list2) elif UI_OPTION == 21: break else: print("💛 Option must be an integer, between 1 to 21.") print() if __name__ == '__main__': # Instantiates a new SLL object SLL_OBJECT = SingleLinkedList() SLL_OBJECT.test_all_methods()
la source
Élargir la réponse de Nick Stinemates
class Node(object): def __init__(self): self.data = None self.next = None class LinkedList: def __init__(self): self.head = None def prepend_node(self, data): new_node = Node() new_node.data = data new_node.next = self.head self.head = new_node def append_node(self, data): new_node = Node() new_node.data = data current = self.head while current.next: current = current.next current.next = new_node def reverse(self): """ In-place reversal, modifies exiting list""" previous = None current_node = self.head while current_node: temp = current_node.next current_node.next = previous previous = current_node current_node = temp self.head = previous def search(self, data): current_node = self.head try: while current_node.data != data: current_node = current_node.next return True except: return False def display(self): if self.head is None: print("Linked list is empty") else: current_node = self.head while current_node: print(current_node.data) current_node = current_node.next def list_length(self): list_length = 0 current_node = self.head while current_node: list_length += 1 current_node = current_node.next return list_length def main(): linked_list = LinkedList() linked_list.prepend_node(1) linked_list.prepend_node(2) linked_list.prepend_node(3) linked_list.append_node(24) linked_list.append_node(25) linked_list.display() linked_list.reverse() linked_list.display() print(linked_list.search(1)) linked_list.reverse() linked_list.display() print("Lenght of singly linked list is: " + str(linked_list.list_length())) if __name__ == "__main__": main()
la source
Mes 2 cents
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
la source
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()
la source
ma double liste liée pourrait être compréhensible pour les noobies. Si vous êtes familier avec DS en C, c'est assez lisible.
# 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()
Bien que de nombreuses simplifications puissent être ajoutées à ce code, j'ai pensé qu'une implémentation brute me serait plus facile à saisir.
la source
Si vous souhaitez simplement créer une simple liste de favoris, reportez-vous à ce code
l = [1, [2, [3, [4, [5, [6, [7, [8, [9, [10]]]]]]]]]]
pour visualiser l'exécution de cette morue Visitez http://www.pythontutor.com/visualize.html#mode=edit
la source