During the last two week, we spent most of the time dealing
with linked lists and I am always wondering why I should use linked lists. Now
that I finally have a week without midterms, I can write down some thoughts.
First of all, what is a linked list? In my own viewpoint,
linked list contains elements with two inner attributes and the first attribute
points to an object while the second attribute referenced the element behind
it. This might be a bit abstract but if you look the following graph, I am sure
you can easily grasp the idea of a linked list.
Like what I just said before, the first attribute points to
a value while the second attribute serves as a pointer pointing to the next
element so if you want to get the second element of the linked list, you need
to follow the references from the first element to reach the second element and
same for the third element, and the fourth element, etc. This idea of
extracting the element from the previous element is the idea of recursion where
the solution to one task depends on the solution to the previous task and the
code is as follows. (Check http://siyangcsc148w3.blogspot.ca/2014/02/what-is-recursion.html
for more on recursion if interested)
However, when I was doing the lab on week 6, I found there
is a serious problem associated with this way of getting elements. As I stated
before, most languages have a maximum recursion limit to prevent the program
from getting stuck in infinite loops, so suppose we have a linked list of 10,000
elements and we want to know the 5,000-th element, then due to the recursion
limit, we cannot get the 5000-th element since it requires 4999 recursion which
is far beyond the maximum stack limit which inevitably resulted in an error. So
the only way to access an element is through step by step, find the previous
element, then to the next element and this might seem quite inefficient
compared with lists where we can just use the index of an element to reach that
element. Thus someone may say, there is no need to have linked list and list is
enough. I will, under most cases, agree with that statement but there are some
cases where linked list is much more efficient since linked list allows for
constant-time(O(1)) insertion and deletion of an element since during insertion
of one element, all we did is to get to that position and change the pointer of
the previous element to the element we want to insert and set the pointer of
the newly added element to the original element in that position while not affecting
other element. However, if we want to insert an element to the middle of a
list, we had to move every element after it to the right to leave space for
inserting the element we wanted. As the
length of lists increased, the time it takes to move all elements to the right
gets longer and longer which is, obviously, quite inefficient. So for random
elements, yes, we should use list since it allows for random indexing but if
for sorted elements where we know exactly which place to insert an element, we
definitely should use linked list. This idea is applied in binary-tree search
in which a tree is built with nodes placed in order, and we could easily insert
a node, changing the pointers or access that element from the root under the
order we designed without concerning too much about the length of the linked
list.
To sum up, when we want to place different object without
any order, a list is a better approach to store these objects since list allows
for random indexing, but if we want to place objects in an order, then linked
list is a better approach since it allows for constant-time insertion and
deletion.
No comments:
Post a Comment