Project: Linked Lists
Learning how nodes work by writing them, and building a linked list, will give you a solid understanding for learning about a more complex subject in the next section, trees.
In our previous lesson, we looked at
Trees; the latter two being core
data structuresto add to your repetoire, and
Nodesbeing the foundation those
data structuresare built upon.
As stated previously, if your language of choice is
Arraysare not a fixed sized in these languages. However, learning how
Nodeswork by writing them, and building a
Linked Listwith them; will give you a working understanding of how
Linked Listswork, and give you a solid, founding principle for tackling the bigger task ahead...
A linked list is a linear collection of data elements called nodes that "point" to the next node by means of a pointer.
Each node holds a single element of data and a link or pointer to the next node in the list.
A head node is the first node in the list, a tail node is the last node in the list. Below is a basic representation of a linked list:
[ NODE(head) ] -> [ NODE ] -> [ NODE(tail) ] -> nil
For a more thorough explanation, use these resources:
In your language of choice...
You will need two classes:
LinkedListclass, which will represent the full list.
Nodeclass, containing a
#valuemethod and a link to the
#next_node, set both as
Build the following methods in your linked list class:
#append(value)adds a new node containing
valueto the end of the list
#prepend(value)adds a new node containing
valueto the start of the list
#sizereturns the total number of nodes in the list
#headreturns the first node in the list
#tailreturns the last node in the list
#at(index)returns the node at the given
#popremoves the last element from the list
#contains?(value)returns true if the passed in value is in the list and otherwise returns false.
#find(value)returns the index of the node containing value, or nil if not found.
#to_srepresent your LinkedList objects as strings, so you can print them out and preview them in the console.The format should be:
( value ) -> ( value ) -> ( value ) -> nil
#insert_at(value, index)that inserts the node with the provided
valueat the given
#remove_at(index)that removes the node at the given
index. (You will need to update the links of your nodes in the list when you remove a node.)