Difference between revisions of "Linked list"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
(expand; copyedit)
(Examples: add)
Line 50: Line 50:
 
   
 
   
 
==Examples==
 
==Examples==
 +
Here is a function that prints a linked list in a readable format:
 +
<syntaxhighlight lang="python">
 +
def print_linked_list(lst):
 +
    """Prints linked list LST.
 +
    >>> lst = link(3, link(1, link(5, link(3))))
 +
    >>> print_linked_list(lst)
 +
    """
 +
    s = '< '
 +
    while lst != empty:
 +
        s = s + repr(first(lst)) + ' '
 +
        lst = rest(lst)
 +
    print(s[:-1] + ' >')
 +
</syntaxhighlight>
 +
 +
Here is a function that searches a linked list for a given item:
 +
<syntaxhighlight lang="python">
 +
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)
 +
</syntaxhighlight>
  
 
==Sources==
 
==Sources==
 
* https://docs.google.com/presentation/d/1qqgY3wk5r0KFnVTjsP8R9dNNaXisGzljXwAaSza1948/edit
 
* https://docs.google.com/presentation/d/1qqgY3wk5r0KFnVTjsP8R9dNNaXisGzljXwAaSza1948/edit

Revision as of 21:28, 4 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 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.

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 ADT

The ADT of a linked list is independent of its implementation. The functions are:

  • link(elem, list) – returns a linked list with elem as the first item and list as the rest of the list
  • first(list) – returns the first field of linked list list
  • rest(list) – returns the rest field of linked list list
  • 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 second(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:

  • LinkedList(elem, list) – returns a linked list with elem as the first item and list as the rest of the list
  • list.first – returns the first field of linked list list
  • list.rest – returns the rest field of linked list list
  • LinkedList.empty – the empty linked 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)
    """
    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)

Sources