Monday, March 16, 2015

CSC148 March 16th: Linked List

In this post, i will be talking about linked lists and linked list nodes, which was covered in class a week ago.  Last week was the second midterm of 148, and i think it went pretty well.  The three quests were very similar to tutorial problems that i have solved before, and i was able to breeze through them without many difficulties.  Now, onto linked lists.

I was taught that there are two main approaches to visualizing linked lists.  One is of lists that contained some data, and possibly another linked list.  This way, inside each linked list could be another linked list, and thus the lists are linked.  The other approach is the one that this course will be taking, which is of objects(nodes) that contain some data, and a reference to another object(node).  With this approach, we will need to defined the object(node) as a class, and also a wrapper that contains the linked list as a whole.  This concept was simple enough, however when it comes to implementing methods that manipulates linked lists, things become more complex.  To me, i think of a linked list as a train, with a beginning node, intermediate nodes, and an ending node.  However, these nodes do not have any form of indexing, and so to manipulate a specific node, i must use a loop that moves down the linked list one node at a time, starting from the beginning.  The difficulty of doing this is that you really don't have a way to knowing exactly the location of the current node in the linked list.  All you know is the data that the current node contains, and its previous and next nodes.  That's why when iterating over linked lists, it is important to be able to clearly visualize how your loop will work, so that you don't end up manipulating the wrong nodes, or worse, severing the link of the linked nodes.

No comments:

Post a Comment