Python Linked List

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:

• the empty list, represented by None, or

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

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.