A Linked List is a sequence of nodes that are connected by
links with a header at the beginning. It
is a linear data structure where each element or node is a separate object.
Every node has a single element which can be a value or an object. Each node apart
from the last has a successor after it. A linked list doesn’t have a fixed
amount of nodes, meaning that it can grow and shrink. This is good because you
might have an unknown amount of objects you have to deal with in a program, but
by using a linked list means you don’t have to worry about the size. However,
by using a linked list, you can’t get direct access to an individual element
within the list. You must start at the head of the list and follow the
references until you get to the item you want.
There are three different types of linked lists:
Linked Lists are a sequence of nodes connected by links that only goes in
one direction, meaning that you can’t go back to the previous node. Each SSL
node contains an element as well as a link to the next node or a null link if
the there is no successor. The header in a SLL will have a link to the first
node in the linked list.
Linked Lists are similar to singly linked lists, but they have two
references, one for the next node and one for the previous node meaning that
you can go in either direction: forward or backwards.
Linked Lists will link the last node back to the head of the list (first
Array List is a child class of AbstractList and it
implements the List interface. They support dynamic arrays that can grow as
needed. A normal array can’t grow or shrink as they have a fixed length when
they are created. For an array you need to know how many elements are to be
held in it beforehand, while, in an array list, you create it with an initial
size but if it is exceeded, it will automatically enlarge the list. If an element
is removed, the array can also be shrunk.
Array lists use arrays for internal storage which means that
it is fast for accessing elements because it implements the random access
interface so it can go right to an element with the index to access it.
Compared to a linked list, an array list is a lot faster in terms of random
access as linked list does not implement the random access interface and has to
traverse through the whole list until you reach the right element. Although it
is slower, linked list can go either backwards or forwards so if you had to
reach element 99 in a list of 100, then you can traverse backwards to get to
the 99th element. It does a sequential scan but this scan is very
Adding and deleting elements at the head or middle of an
array list is slow and takes more time as the elements are being stored in multiple
memory locations and that the elements that come after the point in which you
are inserting or deleting will need to be copied forward or backward. Linked
lists are faster for this because you would only need to update the next and
previous pointers of a node, making it more efficient in terms of speed.
However, if you were to add to the end of the list, then an array list is
faster for this.
Computational complexity of an algorithm is the amount of
resources that is needed in order to run it. Although the resources are exactly
specified, it is usually how much time is taken to run the algorithm and this
is known as time complexity. The time needed depends on the computer that is
being used but the time is usually expresses as the number of needed elementary
operations, which takes a constant time on one computer, and to change by a
constant when the user changes computer. Another way that resource can be
defined in this instance is space complexity which is the size of the memory
that is needed to run the algorithm. An algorithm is efficient if the values of
a function that tests these complexities are small.
The computational complexities of the access, insert and
delete algorithms would mainly be time because for an application or program,
you would want to be able to retrieve an item from the list as quick as
possible and with as little delay as possible. Space complexity would also be
important but not so, compared to time as memory can be reused but we expect
computation to get faster. It has no benefit if it takes extremely long to
solve a problem.
To summarise, array lists are better than a linked list at
accessing an element in a list as the array index gets you to that element,
while in a linked list you must go through every node first until you get to
the right element. Linked lists are usually better than array lists when it
comes to inserting or deleting anywhere in a list. For example, linked lists
are better for inserting or deleting at the beginning of a list because it has
a simple growth pattern where it either adds or removes nodes when it is
needed, but for an array list it must make a copy of the elements that follow
either forwards or backwards. Linked lists are also better for inserting or
deleting in the middle of a list but would take more time as it must search
through the list to get to the point of insertion or deletion. Once the search
for point in the list is done, the speed in which it inserts or deletes would
be similar to inserting or deleting at the start. However, linked lists can be
time consuming if you were to insert or delete at the end of the list and the
last element is unknown but in an array list, the algorithm runs quite fast for
inserting and deleting at the end.