Lists Part II: Basic Operations
Data Structures in Ruby
I recommend reading yesterday’s post if you haven’t already. It covers the basics of lists.
The three basic operations supported by lists are searching, insertion, and deletion.
Searching for data in a list entails visiting each node, one at a time, until either the data has been found or the tail of the list has been reached. Because search requires sequentially traversing the list, it is a linear time operation.
Insertion into a list is performed by replacing the current head of a list with a new node. Because nodes are inserted at the head of a list, no iteration is required. Therefore, insertion is a constant time operation. Insertion into a list is a push-front operation because it adds a node to the front of a list.
Insertion can be implemented as either an iterative or a recursive operation. We’ll compare both approaches in a future post. For now, we’ll use a recursive approach.
Deletion from a list takes a doomed node ( the node to be deleted ) as a parameter. If the doomed node is at the head of the list, then the head must be updated so that it points to the successor ( the “next node” ) of the doomed node. Otherwise, the predecessor of the doomed node must be updated to point to the successor of the doomed node. Deletion, as with searching, must traverse the list from head to tail, or until the doomed node is discovered and removed. It is therefore a linear time operation.
Study the code for the deletion operation carefully and practice writing it on your own. Build an intuitive understanding of what is happening. Visualize the list as you transform it with all three basic operations.
In order to use the deletion operation, first find a target node, then delete it.
There are three basic operations supported by lists: searching, insertion, and deletion. Both searching and deletion require a sequential traversal of the nodes in a list and therefore they are both linear time operations. Insertion is a push-front operation in which the inserted node replaces the head of the list. Insertion is thus a constant time operation.
Q & A
What are the three basic operations supported by lists?
Searching, insertion, and deletion.
How do you traverse a list?
By proceeding sequentially, from a the head of the list toward the tail of the list.
How do you find some specific piece of data in a list?
You can find data in a list by visiting each node in the list, one by one, until either every node in the list has been considered or the data being searched for is found.
How long does it take to search a list?
A list can be searched in linear time. The reason that searching a list is a linear time operation is that every node in the list must be visited.
How do you insert a new node into a list?
In order to insert a new node into a list, have the head of the list point to the new node and have the new node point to the previous list head as its successor ( “next node” ).
How long does it take to insert a new node into a list?
Insertion into a list is a constant time operation, because it is a push-front operation, occurring at the head of the list each time it is performed.
What is a push-front operation?
A push-front operation is an operation in which a new item is added at the front of a data structure.
How do you remove a node from a list?
First, locate the doomed node. Next, update the predecessor of the doomed node so that it points to the successor of the doomed node.
How do you remove the head of a list?
Point the list’s head at the successor of the doomed head node.
What needs to be done if you remove the current tail of a list?
Update the predecessor of the doomed tail node so that it’s “next node” is nil.
What needs to be done if you remove the only node in a list?
Set the head of the list to nil.
How fast is the removal operation?
Because each node in a list must be visited, removal from a list is a linear time operation.
In part III of this series we’ll compare lists and arrays, discussing the advantages and disadvantages of each. If you enjoyed this post and want to stay current on updates to this series, please be sure to recommend this post and follow me below. Go to part III now.