Menu
For some needs, a deque may also be useful. You can add and remove items on both ends of a deque at O(1) cost.
from collections import deque
d = deque([1,2,3,4])
print d
for x in d:
print x
print d.pop(), d
I wrote this up the other day
#! /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()
Here is some list functions based on Martin v. Löwis's representation:
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")
where w = sys.stdout.write
Although doubly linked lists are famously used in Raymond Hettinger's ordered set recipe, singly linked lists have no practical value in Python.
I've never used a singly linked list in Python for any problem except educational.
Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist, Chapter 17: Linked lists:
A linked list is either:
a node that contains a cargo object and a reference to a linked list.
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")
The accepted answer is rather complicated. Here is a more standard design:
L = LinkedList()
L.insert(1)
L.insert(1)
L.insert(2)
L.insert(4)
print L
L.clear()
print L
It is a simple LinkedList class based on the straightforward C++ design and Chapter 17: Linked lists, as recommended by 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__()
Immutable lists are best represented through two-tuples, with None representing NIL. To allow simple formulation of such lists, you can use this function:
def mklist(*args):
result = None
for element in reversed(args):
result = (element, result)
return result
To work with such lists, I'd rather provide the whole collection of LISP functions (i.e. first, second, nth, etc), than introducing methods.
Here's a slightly more complex version of a linked list class, with a similar interface to python's sequence types (ie. supports indexing, slicing, concatenation with arbitrary sequences etc). It should have O(1) prepend, doesn't copy data unless it needs to and can be used pretty interchangably with tuples.
It won't be as space or time efficient as lisp cons cells, as python classes are obviously a bit more heavyweight (You could improve things slightly with "__slots__ = '_head','_tail'" to reduce memory usage). It will have the desired big O performance characteristics however.
Example of usage:
>>> 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])
Implementation:
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With