Lista enlazada de Python

¿Cuál es la forma más fácil de usar una lista vinculada en python? En el esquema, una lista enlazada se define simplemente por '(1 2 3 4 5) . Las listas de Python, [1, 2, 3, 4, 5] , y las tuplas, (1, 2, 3, 4, 5) , no son, de hecho, listas vinculadas, y las listas vinculadas tienen algunas propiedades agradables como constantes concatenación de tiempo, y poder hacer referencia a partes separadas de ellos. ¡Hazlos inmutables y es muy fácil trabajar con ellos!

Aquí hay algunas funciones de lista basadas en la representación de 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") 

donde w = sys.stdout.write

Si bien las listas con enlaces dobles se usan en la receta ordenada del juego de Raymond Hettinger, las listas con enlaces individuales no tienen valor práctico en Python.

Nunca he usado una lista enlazada individualmente en Python para ningún problema excepto educativo.

Thomas Watnedal sugirió un buen recurso educativo Cómo pensar como un científico informático, Capítulo 17: Listas vinculadas :

Una lista enlazada es:

  • la lista vacía, representada por Ninguna, o
  • un nodo que contiene un objeto de carga y una referencia a una lista enlazada.

     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") 

Para algunas necesidades, un deque también puede ser útil. Puede agregar y eliminar elementos en ambos extremos de un deque a un costo de O (1).

 from collections import deque d = deque([1,2,3,4]) print d for x in d: print x print d.pop(), d 

Escribí esto el otro día.

 #! /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 respuesta aceptada es bastante complicada. Aquí hay un diseño más estándar:

 L = LinkedList() L.insert(1) L.insert(1) L.insert(2) L.insert(4) print L L.clear() print L 

Es una clase simple de LinkedList basada en el diseño sencillo de C ++ y en el Capítulo 17: Listas enlazadas , según lo recomendado por 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__() 

Las listas inmutables se representan mejor a través de dos tuplas, y ninguna representa NIL. Para permitir una formulación simple de dichas listas, puede utilizar esta función:

 def mklist(*args): result = None for element in reversed(args): result = (element, result) return result 

Para trabajar con dichas listas, prefiero proporcionar toda la colección de funciones LISP (es decir, primero, segundo, enésimo, etc.), que introducir métodos.

Aquí hay una versión ligeramente más compleja de una clase de lista vinculada, con una interfaz similar a los tipos de secuencia de python (es decir, admite indexación, corte, concatenación con secuencias arbitrarias, etc.). Debe tener O (1) prepend, no copia los datos a menos que sea necesario y se puede usar de manera intercambiable con las tuplas.

No será tan eficiente en cuanto al espacio o el tiempo como las celdas Lisp, ya que las clases de python son obviamente un poco más pesadas (podría mejorar un poco las cosas con ” __slots__ = '_head','_tail' ” para reducir el uso de memoria). Sin embargo, tendrá las características de rendimiento grandes deseadas.

Ejemplo de uso:

 >>> 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]) 

Implementación:

 import itertools class LinkedList(object): """Immutable linked list class.""" def __new__(cls, l=[]): if isinstance(l, LinkedList): return l # Immutable, so no copy needed. i = iter(l) try: head = i.next() except StopIteration: return cls.EmptyList # Return empty list singleton. tail = LinkedList(i) obj = super(LinkedList, cls).__new__(cls) obj._head = head obj._tail = tail return obj @classmethod def cons(cls, head, tail): ll = cls([head]) if not isinstance(tail, cls): tail = cls(tail) ll._tail = tail return ll # head and tail are not modifiable @property def head(self): return self._head @property def tail(self): return self._tail def __nonzero__(self): return True def __len__(self): return sum(1 for _ in self) def __add__(self, other): other = LinkedList(other) if not self: return other # () + l = l start=l = LinkedList(iter(self)) # Create copy, as we'll mutate while l: if not l._tail: # Last element? l._tail = other break l = l._tail return start def __radd__(self, other): return LinkedList(other) + self def __iter__(self): x=self while x: yield x.head x=x.tail def __getitem__(self, idx): """Get item at specified index""" if isinstance(idx, slice): # Special case: Avoid constructing a new list, or performing O(n) length # calculation for slices like l[3:]. Since we're immutable, just return # the appropriate node. This becomes O(start) rather than O(n). # We can't do this for more complicated slices however (eg [l:4] start = idx.start or 0 if (start >= 0) and (idx.stop is None) and (idx.step is None or idx.step == 1): no_copy_needed=True else: length = len(self) # Need to calc length. start, stop, step = idx.indices(length) no_copy_needed = (stop == length) and (step == 1) if no_copy_needed: l = self for i in range(start): if not l: break # End of list. l=l.tail return l else: # We need to construct a new list. if step < 1: # Need to instantiate list to deal with -ve step return LinkedList(list(self)[start:stop:step]) else: return LinkedList(itertools.islice(iter(self), start, stop, step)) else: # Non-slice index. if idx < 0: idx = len(self)+idx if not self: raise IndexError("list index out of range") if idx == 0: return self.head return self.tail[idx-1] def __mul__(self, n): if n <= 0: return Nil l=self for i in range(n-1): l += self return l def __rmul__(self, n): return self * n # Ideally we should compute the has ourselves rather than construct # a temporary tuple as below. I haven't impemented this here def __hash__(self): return hash(tuple(self)) def __eq__(self, other): return self._cmp(other) == 0 def __ne__(self, other): return not self == other def __lt__(self, other): return self._cmp(other) < 0 def __gt__(self, other): return self._cmp(other) > 0 def __le__(self, other): return self._cmp(other) <= 0 def __ge__(self, other): return self._cmp(other) >= 0 def _cmp(self, other): """Acts as cmp(): -1 for self b: return 1 try: A.next() return 1 # a has more items. except StopIteration: pass try: B.next() return -1 # b has more items. except StopIteration: pass return 0 # Lists are equal def __repr__(self): return "LinkedList([%s])" % ', '.join(map(repr,self)) class EmptyList(LinkedList): """A singleton representing an empty list.""" def __new__(cls): return object.__new__(cls) def __iter__(self): return iter([]) def __nonzero__(self): return False @property def head(self): raise IndexError("End of list") @property def tail(self): raise IndexError("End of list") # Create EmptyList singleton LinkedList.EmptyList = EmptyList() del EmptyList 

llist – Tipos de datos de listas vinculadas para Python

El módulo llist implementa estructuras de datos de listas vinculadas. Admite una lista doblemente enlazada, es decir, dllist y una lista de estructura de datos enlazada individualmente.

objetos dllist

Este objeto representa una estructura de datos de lista doblemente enlazada.

first

Primer objeto dllistnode en la lista. None si la lista está vacía.

last

Último objeto dllistnode en la lista. Ninguna si la lista está vacía.

Los objetos dllist también soportan los siguientes métodos:

append(x)

Agregue x al lado derecho de la lista y devuelva el dllistnode insertado.

appendleft(x)

Agregue x al lado izquierdo de la lista y devuelva el dllistnode insertado.

appendright(x)

Agregue x al lado derecho de la lista y devuelva el dllistnode insertado.

clear()

Eliminar todos los nodos de la lista.

extend(iterable)

Agregue elementos de iterable al lado derecho de la lista.

extendleft(iterable)

Agregue elementos de iterable al lado izquierdo de la lista.

extendright(iterable)

Agregue elementos de iterable al lado derecho de la lista.

insert(x[, before])

Agregue x al lado derecho de la lista si before no se especifica, o inserte x al lado izquierdo de dllistnode before . Regresar dllistnode insertado.

nodeat(index)

Devuelve el nodo (de tipo dllistnode ) en el index .

pop()

Elimine y devuelva el valor de un elemento desde el lado derecho de la lista.

popleft()

Elimine y devuelva el valor de un elemento del lado izquierdo de la lista.

popright()

Eliminar y devolver el valor de un elemento desde el lado derecho de la lista

remove(node)

Elimine el node de la lista y devuelva el elemento que estaba almacenado en él.

objetos dllistnode

clase llist.dllistnode([value])

Devuelve un nuevo nodo de lista con doble enlace, inicializado (opcionalmente) con value .

dllistnode objetos dllistnode proporcionan los siguientes atributos:

next

Siguiente nodo en la lista. Este atributo es de solo lectura.

prev

Nodo anterior en la lista. Este atributo es de solo lectura.

value

Valor almacenado en este nodo. Comstackdo de esta referencia

sllist

class llist.sllist([iterable]) Devuelve una nueva lista enlazada individualmente inicializada con elementos de iterable . Si iterable no está especificado, el nuevo sllist está vacío.

Se define un conjunto similar de atributos y operaciones para este objeto sllist . Vea esta referencia para más información.

 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()) 

Basé esta función adicional en 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 

El método que tiene agrega el nuevo nodo al principio, mientras que he visto muchas implementaciones que generalmente agregan un nuevo nodo al final, pero sea lo que sea, es divertido hacerlo.

Lo siguiente es lo que se me ocurrió. Es similar a la de Riccardo C. , en este hilo, excepto que imprime los números en orden en lugar de al revés. También hice del objeto LinkedList un Iterador de Python para imprimir la lista como si fuera una lista de Python normal.

 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 """ 

Acabo de hacer esto como un juguete divertido. Debería ser inmutable siempre y cuando no toques los métodos con el guión bajo del prefijo, e implementa un montón de magia de Python como indexación y len .

Cuando use listas vinculadas inmutables, considere usar la tupla de Python directamente.

 ls = (1, 2, 3, 4, 5) def first(ls): return ls[0] def rest(ls): return ls[1:] 

Es realmente así de fácil, y puedes mantener las funciones adicionales como len (ls), x en 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) 

He puesto una clase de lista enlazada individualmente de Python 2.xy 3.x en https://pypi.python.org/pypi/linked_list_mod/

Se probó con CPython 2.7, CPython 3.4, Pypy 2.3.1, Pypy3 2.3.1 y Jython 2.7b2, y viene con un buen conjunto de pruebas automatizadas.

También incluye clases de LIFO y FIFO.

Aunque no son inmutables.

 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 (ie 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 

Lista de clases vinculadas

 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 

Uso

 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(), '-|----> ', 

Salida

 | 55 | 25 -|----> | 25 | 10 -|----> | 10 | --> None 

Aquí está mi implementación 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) 

Salida:

 Data 1: Next -> Data 2: Next -> Data 34: Next -> Data 4: Next -> None 

Aquí está mi solución:

Implementación

 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 

Uso

 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) 

Idea original de implementación

http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

Creo que la implementación a continuación llena el proyecto de ley con bastante gracia.

 '''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) 

En primer lugar, asumo que quieres listas enlazadas. En la práctica, puede usar collections.deque , cuya implementación actual de CPython es una lista de bloques doblemente enlazada (cada bloque contiene una matriz de 62 objetos de carga). Subsume la funcionalidad de la lista enlazada. También puede buscar una extensión C llamada llist en pypi. Si desea una implementación de la lista enlazada ADT de Python puro y fácil de seguir, puede echar un vistazo a mi siguiente implementación mínima.

 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) 

Ejemplo de una lista doblemente enlazada (guardar como linklist.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 (save as 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 

Mis 2 centavos

 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() 

my double Linked List might be understandable to noobies. If you are familiar with DS in C, this is quite readable.

 # 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() 

Though many more simplifications can be added to this code, I thought a raw implementation would me more grabbable.

If you want to just create a simple liked list then refer this code

l=[1,[2,[3,[4,[5,[6,[7,[8,[9,[10]]]]]]]]]]

for visualize execution for this cod Visit http://www.pythontutor.com/visualize.html#mode=edit