Linked list
A linked list is a recursive data structure that represents a sequence of elements. It consists of a series of nodes. Each node contains a piece of data, as well as a pointer to the next node. The last element in the list is the empty linked list. The piece of data is called the "first" field of that linked list, and the pointer to the next node is called the "rest" field.
Contents
Types
In a straightforward linked list, a node's first field contains a value (string, number, etc.), while the second field will contain another linked list. Using this structure, a series of nested linked lists can form a list of values.
A deep linked list is slightly different. The first and second fields contain another linked list. A good way to visualize linked lists is to draw them out.
ADT and implementations
The ADT of a linked list is independent of its implementation.
Functional ADT
The ADT of a linked list is independent of its implementation. The functions are:

link(elem, list)
– returns a linked list withelem
as the first item andlist
as the rest of the list 
first(list)
– returns the first field of linked listlist

rest(list)
– returns the rest field of linked listlist

empty
– the empty linked list
The following are implementations of the ADT:
 with tuples:
empty = lambda: 42 def link(element, list=empty): return (element, list) def first(list): return list[0] def rest(list): return list[1]
 with
cons
:
empty = lambda: 42 def link(element, list=empty): return cons(element, list) def first(list): return car(list) def rest(list): return cdr(list)
OOP ADT
The OOP ADT is:

Link(elem, list)
– returns a linked list withelem
as the first item andlist
as the rest of the list 
list.first
– returns the first field of linked listlist

list.rest
– returns the rest field of linked listlist

Link.empty
– the empty linked list
The basic code can be seen below. Note that list.first
and list.rest
are implemented as instance attributes, Link.empty
as a class attribute, and Link(first, rest)
via __init__
:
class Link: """A recursive list, with Python integration.""" empty = None def __init__(self, first, rest=empty): self.first = first self.rest = rest def __repr__(self): if self.rest is Link.empty: rest = '' else: rest = ', ' + repr(self.rest) return 'Link({}{})'.format(self.first, rest) def __str__(self): if self.rest is Link.empty: rest = '' else: rest = ' ' + str(self.rest)[2:2] return '< {}{} >'.format(self.first, rest)
Operations
The recursive structure of a linked list suggests recursive algorithms for operations. Generally, the base case will be if the current node is the empty list. The recursive step will involve recursing on the rest of the list.
A linked list can also be operated on using iteration: a while loop that continues until the current node is the empty list and repeatedly updating a variable to the rest of the list.
Examples
Here is a function that prints a linked list in a readable format:
def print_linked_list(lst): """Prints linked list LST. >>> lst = link(3, link(1, link(5, link(3)))) >>> print_linked_list(lst) < 3 1 5 3 > """ s = '< ' while lst != empty: s = s + repr(first(lst)) + ' ' lst = rest(lst) print(s[:1] + ' >')
Here is a function that searches a linked list for a given item:
def contains(lst, elem): """Returns True if linked list LST contains ELEM. >>> lst = link(3, link(1, link(5, link(3)))) >>> contains(lst, 5) True >>> contains(lst, 4) False """ if lst == empty: return False return first(lst) == elem or contains(rest(lst), elem)