Difference between revisions of "Linked list"
[checked revision]  [checked revision] 
m ({{Startclass}}) 
(expand; copyedit) 

Line 1:  Line 1:  
{{Startclass}}  {{Startclass}}  
−  A '''linked list''' is a recursive data structure that represents a sequence of elements  +  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 ==  
Line 7:  Line 7:  
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  +  == 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: 
−  <syntaxhighlight lang="python">  +  * 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 second(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 40:  
def rest(list):  def rest(list):  
return cdr(list)  return cdr(list)  
+  </syntaxhighlight></blockquote>  
−  +  == OOP ADT ==  
−  +  The [[Objectoriented programmingOOP]] ADT is:  
−  +  * <code>LinkedList(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>list.first</code> – returns the first field of linked list <code>list</code>  
−  +  * <code>list.rest</code> – returns the rest field of linked list <code>list</code>  
−  +  * <code>LinkedList.empty</code> – the empty linked list  
−  </  +  
−  +  
−  +  
−  +  
==Examples==  ==Examples==  
==Sources==  ==Sources==  
* https://docs.google.com/presentation/d/1qqgY3wk5r0KFnVTjsP8R9dNNaXisGzljXwAaSza1948/edit  * https://docs.google.com/presentation/d/1qqgY3wk5r0KFnVTjsP8R9dNNaXisGzljXwAaSza1948/edit 
Revision as of 21:12, 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.
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.
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 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 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

LinkedList.empty
– the empty linked list