Difference between revisions of "Linked list"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
m ({{Start-class}})
(Remove reverse for now)
 
(9 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Start-class}}
 
{{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 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 ==
 
== 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.
 
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. <!-- add example -->  
+
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. <!-- add example -->
  
== Functional implementation ==
+
[[File:Deep_list.png|alt=A deep list is a linked list with possibly another linked list as an element of the linked list. We have a deep list in this picture because the third (and final) element of this list is another linked list: <code>link(3, link(4, empty))</code>]]
=== With tuples ===
+
  
=== With <code>cons</code> ===
+
== ADT and implementations ==
<syntaxhighlight lang="python">
+
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:
 +
* <code>link(elem, list)</code> – returns a linked list with <code>elem</code> as the first item and <code>list</code> as the rest of the list
 +
* <code>first(list)</code> – returns the first field of linked list <code>list</code>
 +
* <code>rest(list)</code> – returns the rest field of linked list <code>list</code>
 +
* <code>empty</code> – the empty linked list
 +
 
 +
The following are implementations of the ADT:
 +
* with tuples:
 +
<blockquote style="margin: 1em 1.6em;"><syntaxhighlight lang="python">
 
empty = lambda: 42
 
empty = lambda: 42
  
def link(element, list):
+
def link(element, list=empty):
 +
    return (element, list)
 +
 
 +
def first(list):
 +
    return list[0]
 +
 
 +
def rest(list):
 +
    return list[1]
 +
</syntaxhighlight></blockquote>
 +
* with <code>cons</code>:
 +
<blockquote style="margin: 1em 1.6em;"><syntaxhighlight lang="python">
 +
empty = lambda: 42
 +
 
 +
def link(element, list=empty):
 
     return cons(element, list)
 
     return cons(element, list)
  
Line 22: Line 45:
 
def rest(list):
 
def rest(list):
 
     return cdr(list)
 
     return cdr(list)
 +
</syntaxhighlight></blockquote>
  
def print_linked_list(list):
+
=== OOP ADT ===
    s = '<'
+
The [[Object-oriented programming|OOP]] ADT is:
     while list != empty:
+
* <code>Link(elem, list)</code> – returns a linked list with <code>elem</code> as the first item and <code>list</code> as the rest of the list
         s = s + repr(first(list)) + ' '
+
* <code>list.first</code> – returns the first field of linked list <code>list</code>
         list = rest(list)
+
* <code>list.rest</code> – returns the rest field of linked list <code>list</code>
     return s[:-1] + '>'
+
* <code>Link.empty</code> – the empty linked list
 +
 
 +
The basic code can be seen below. Note that <code>list.first</code> and <code>list.rest</code> are implemented as instance attributes, <code>Link.empty</code> as a class attribute, and <code>Link(first, rest)</code> via <code>__init__</code>:
 +
<syntaxhighlight lang="python">
 +
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)
 
</syntaxhighlight>
 
</syntaxhighlight>
  
==Accessors==
+
== Operations ==
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.  
+
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==
 
==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)
 +
    < 3 1 5 3 >
 +
    """
 +
    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

Latest revision as of 13:48, 25 March 2016

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.

A deep list is a linked list with possibly another linked list as an element of the linked list. We have a deep list in this picture because the third (and final) element of this list is another linked list: link(3, link(4, empty))

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

Sources