Linked list

From CS 61A Wiki
Revision as of 14:23, 2 July 2014 by Axis (Talk | contribs)

Jump to: navigation, search

A linked list is a recursive data structure that represents a sequence of elements.. It consists of a series of nodes. Each node has two fields, denoted first and rest.


In a straight-forward 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.

Functional implementation

With tuples

With cons

empty = lambda: 42
def link(element, list):
    return cons(element, list)
def first(list):
    return car(list)
def rest(list):
    return cdr(list)
def print_linked_list(list):
    s = '<'
    while list != empty:
        s = s + repr(first(list)) + ' '
        list = rest(list)
    return s[:-1] + '>'


In order to traverse and manipulate a linked list, the user must utilize linked list methods. The first function takes a linked list as its argument and returns the first element of that linked list. The rest function takes a linked list as its argument and returns the remainder of the argument linked list, which is the smaller linked list that comprises the rest of the argument linked list.