¿Cuál es la forma más fácil de usar una lista vinculada en Python? En Scheme, una lista enlazada se define simplemente por '(1 2 3 4 5).

listas de Python, [1, 2, 3, 4, 5]y tuplas, (1, 2, 3, 4, 5), no son, de hecho, listas enlazadas, y las listas enlazadas tienen algunas buenas propiedades, como la concatenación en tiempo constante y la posibilidad de hacer referencia a partes separadas de ellas. ¡Hazlos inmutables y es muy fácil trabajar con ellos!

Para algunas necesidades, un deque también puede ser útil. Puede agregar y eliminar elementos en ambos extremos de una 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

esto lo escribi el otro dia

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

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

Aunque las listas doblemente enlazadas son famosamente utilizadas en el libro de Raymond Hettinger receta ordenadalas listas enlazadas individualmente no tienen ningún valor práctico en Python.

He Nunca usó una lista enlazada individualmente en Python para cualquier problema, excepto educativo.

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

Una lista enlazada es:

• la lista vacía, representada por Ninguno, 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")
  

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 un sencillo LinkedList clase basada en el sencillo diseño de C++ y Capítulo 17: Listas enlazadassegú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, con None representando NIL. Para permitir una formulación simple de tales listas, puede usar esta función:

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

Para trabajar con tales listas, prefiero proporcionar la colección completa de funciones LISP (es decir, primera, segunda, enésima, etc.), que introducir métodos.

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

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

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<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 — Tipos de datos de listas enlazadas para Python

El módulo llist implementa estructuras de datos de listas enlazadas. Admite una lista doblemente enlazada, es decir dllist y una estructura de datos de enlace simple sllist.

objetos de lista dll

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

first

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

last

Ultimo dllistnode objeto en la lista. Ninguno si la lista está vacía.

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

append(x)

Agregar x al lado derecho de la lista y volver insertado dllistnode.

appendleft(x)

Agregar x al lado izquierdo de la lista y volver insertado dllistnode.

appendright(x)

Agregar x al lado derecho de la lista y volver insertado dllistnode.

clear()

Elimina todos los nodos de la lista.

extend(iterable)

Agregar elementos de iterable al lado derecho de la lista.

extendleft(iterable)

Agregar elementos de iterable al lado izquierdo de la lista.

extendright(iterable)

Agregar elementos de iterable al lado derecho de la lista.

insert(x[, before])

Agregar x al lado derecho de la lista si before no se especifica, o insertar x al lado izquierdo de dllistnode before. Devolución insertada dllistnode.

nodeat(index)

Nodo de retorno (de tipo dllistnode) a index.

pop()

Elimina y devuelve el valor de un elemento del lado derecho de la lista.

popleft()

Elimina y devuelve el valor de un elemento del lado izquierdo de la lista.

popright()

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

remove(node)

Eliminar node de la lista y devolver el elemento que se almacenó en él.

dllistnode objetos

clase llist.dllistnode([value])

Devuelve un nuevo nodo de lista doblemente enlazado, inicializado (opcionalmente) con value.

dllistnode Los objetos 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.
Compilado de esta referencia

lista

clase llist.sllist([iterable])
Devuelve una nueva lista enlazada individualmente inicializada con elementos de iterable. Si no se especifica iterable, el nuevo sllist esta vacio.

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