Like Week 8, Week 9 was also a busy week since I had multiple assignments and tests, including the second term test for CSC148. I mentioned in last week’s slog that I didn’t thoroughly study linked list, and that I hope nothing related to deleting nodes will be on the test. Unfortunately, according to Murphy’s Law, “anything that can go wrong, will go wrong.” On the third and last question of the term test, I had to incorporate the idea of deleting nodes. After the test, I discussed my answers with fellow classmates and not surprisingly, my answer for question 3 was wrong. The good thing was my answers for question 1 and 2 were correct. So hopefully, part marks can be given on my attempt at question 3.
Because of my lack of understanding regarding linked lists, I decided to re-learn the class materials. With the help of my friend a person's slog, I finally learned the structure and implementation of linked list. One important tool that my friend taught me in order to understand linked list is to draw pictures. To begin, linked lists are lists made up of connecting nodes. It is shaped like a chain where each node is connect to only one node. In technical terms, linked list represents a sequence of a collection of objects (nodes) with a value and a reference to other similar objects. To understand its structure better, drawing pictures are really helpful. Here is a pictorial representation of linked list:
To be more specific, linked list consists of two classes. The first one is called LLNode and it represents one single item (node) in the linked list. This object stores the value of a particular node, and the value of the next node connected to that particular node (represented by the ‘next’ attribute in the init method). The diagram above refers to three distinct nodes connected in the form of a linked list. The first node has the value 1, and its ‘next’ attribute refers to the second node with the value 2. The second class is called LinkedList, which represents the entire list with nodes connected in a particular order. It contains three main attributes, the first being the value of the frontmost node (stored by the variable ‘front’), the second being the value of the last node of the list (stored by the variable ‘back’), and the last being the number of nodes in the linked list (stored by the variable ‘size’). In the above diagram, ‘front’ refers to 1, and ‘back’ refers to the value 3, whereas size refers to 3 since there are three nodes in total. Furthermore, many other methods such as append, delete_front, prepend and __contains__ are also implemented in the class LinkedList.
The part that I had the most trouble with was deleting a node. Now that I learned to draw helpful diagrams, the concept of deletion doesn’t seem as hard. To delete a node with a designated value after its first occurrence involves assigning a variable called cur_node (current node), which keeps track of the value of the current node. Here is what the code looks like:
Basically, the code means if the first node exists and has a value, make the variable cur_node refer to that first node, represented by lnk.front. Then continue to traverse down the list looking for the node with the selected value. In case the entire list does not contain the value we are looking for, we have to accompany the while loop with the condition that cur_node always has to exist (not None). Furthermore, if we did not find the node with the value we are looking and the list still has unvisited nodes, assign cur_node to the next, upcoming node. Now, the while loop either terminates if we already searched through the entire list or if we found the node with the value we are looking. If after traversing the entire list, no node contains the value, the if statement determines what to do. If cur_node refers to the value None, it means that the entire linked list does not contain the value we are searching for, hence nothing happens. However, if cur_node exists, we either delete the node after it (if cur_node is not the last node of the linked list), or we do nothing since cur_node is already the last node of the list (the ‘back’ of the list). Here is a diagram:
If the value we are searching for is 55, cur_node will at first refer to 17. Since 17 does not equal to the value we are looking for and cur_node is not None, cur_node is now assigned to be the next node with the value 23. Just like 17, 23 also does not equal to 55, hence cur_node now refers to 55. Since cur_node == 55 == value, the while loop terminates. According to the if statement, cur_node and cur_node.nxt both exists. Hence, the body of the if statement is being executed. Since lnk.back is not cur_node.nxt (meaning node 72 is not the last node of the list), cur_node.nxt will be equal to cur_node.nxt.nxt. This means in the node with the value 55, its attribute ‘next’ will now refer to the node with the value of 14 instead of 72, hence deleting the node with the value 72. Moreover, the size will be decrease by the value 1. Now, if 14 is the value we are looking for, cur_node will end up referring to node with value 14. Since 14 is the last node of the list, cur_node.nxt is None, and nothing happens because the if statement never gets executed. Let’s say the value we are looking for is 25, which is not in the list. In the end after traversing through the entire linked list, cur_node will refer to None, since cur_node = 14 and cur_node.nxt will be None. Similar to the previous example, nothing will happen.
In conclusion, drawing pictures are sometimes critical for understanding complex data structures. Despite the fact that I was occupied with tons of work last week, I am really satisfied with myself and my problem solving attitude. In the end, I want to thank the person who wrote the slog http://egq148.blogspot.ca/ since it helped me understand linked list and how it works.
No comments:
Post a Comment