Difference between revisions of "Linked list"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(add; copyedit)
m ({{Start-class}})
Line 1: Line 1:
 +
{{Start-class}}
 
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''.
 
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''.
  

Revision as of 14:23, 2 July 2014

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.

Types

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] + '>'

Accessors

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.

Examples

Sources