Arrays and Linked Lists

Arrays and Linked
Lists
A comparative study of these interrelated data structures

Arrays
• An array is a collection of items stored at contiguous memory
locations. The idea is to store elements together so that referencing
them via a base address is very easy. It is finite, ordered and
homogeneous in nature!
• An important thing to note is that the address of the array is the
address of the first element of the array!
Types of Arrays
• One Dimensional
• Multi Dimensional
Algorithms
• Traversing an array
• Visiting every elements of the array one by one in an ordered fashion.
• Algorithm
• Start
• Declare a pointer to the array base address
• Visit position
• Increment pointer
• Repeat steps 3 and 4 until the array has been fully traversed
• Exit
Algorithms
• Insertion
• Need to insert an element on a given position. The value along with its
position will be given as the user input.
• There are two cases associated with insertion to an array
• After the last element
• Before or on the position of the last element
• After the last element
• The insertion becomes trivial. If the user inputs a position at the first free element, given
that the input is within the capacity of the array, we just set the value of the array to the
user input at the position desired. The size of the array also increases by one.
• However, if the user tries to input a position greater than the bounds of the array or in a
position that creates a “bubble” in the array, the insertion operation fails.
Insertion
Insertion
• Before or at the position of the last element
• Requires a backwards traversal till the array position. At every position, you
copy over the values one place over to the right and continue the loop until
you’ve reached the position that the user has given as an input.
• This obviously requires checking whether the size hasn’t exceeded the
capacity of the array. The size of the array is also incremented given that the
insertion operation was successful.
Deletion
• There are also two cases related with deletion from an array.
• Deleting the last element
• Deleting an element before or on the position of the last element.
• Deleting the last element

• This case is trivial. We just need to decrement the ‘size’ pointer by one so that
our array size gets reduced by one. This removes the last element from our
logical view of the array.
Deletion
• Deleting an element before or on the position of the last element.
• Requires a forwards traversal till the array position. At every position, you copy over the
values one place over to the left and continue the loop until you’ve reached the position
that the user has given as an input.
• This obviously requires checking whether the array isn’t empty to begin with. If the array
isn’t empty, the size is decremented by one after the deletion operation is performed
successfully.
Linked Lists
• As good as arrays seem for data storage, they are not the most ideal
data structure out there. Since our data doesn’t really have an upper
bound on its size and since insertion and deletion on an array was
taking O(n) of time, where n was the size of the array, a linked list
would be a better data structure since it eliminates many problems in
such use cases.
What are Linked Lists?
• A linked list is basically a collection of nodes that contains a data value
and some sort of connection to the next node in the sequence.
• The node contains
• Some information
• A pointer to the next node in the sequence
• A linked list requires some sort of an indicator
for the first element. We typically name this as the head of the linked
list. It is vital to keep track of this pointer and use it properly since a
wrong action could lead to the user losing the entire linked list!
Linked Lists
• We can also build this data structure by keeping extra information
such as the tail pointers, the middle pointer, but these depend on the
developer or the user requirements.
• We have different flavours of linked lists too. These have higher
storage requirements but present better solutions to the problem of
insertion, deletion and traversal of the linked lists
• Singly Linked Lists
• Doubly Linked Lists
• Circular Linked Lists
• Now, we shall focus on Singly Linked Lists
Singly Linked List
Algorithms
• Traversal
• Traversal is simple with linked lists. We start with a reference to the head
pointer and we visit each and every node. After visiting a node, we take the
pointer to the next node and we do so until we’ve visited all the nodes.
Insertion
• Insertion. We expect the user gives us the value he/she wants to enter
along with its position.
• Insertion at the head
• Insertion at the end
• Insertion in the middle
• Insertion in the head

• This is pretty simple to implement. However, the order of operations we perform
is critical! We first create a new node whose address value points to the current
head. We then set the linked list head to the new node’s address. This operation
may seem simple but it is incredibly easy to mess up and lose the entire linked
list!
Insertion
• Insertion in the middle
• This is a difficult operation to perform. The most common method uses the
use of two pointers in order to achieve this operation. One pointer follows the
other and they, together, determine the position to add the element.
• Let’s take an example and add a node at the second index.
Insertion at the tail
• This really is an extension to the previous insertion strategy. However,
we would also want to consider the fact that the index entered by the
user may be out of range. This is similar to the bubble problem we
saw in arrays. It violates the linear property of linked lists.
Deletion
• Deletion also has three cases. The user inputs the index of the node
he/she wants to delete and our algorithm removes the node from the
linked list. We will discuss about them one by one
• Deletion from the head
• Deletion from the tail
• Deletion from the middle
• Deletion from the head
• As with insertion, the order in which we perform the operations matters a lot.
We first hold a reference to the current head of the linked list. We then change
the head to be the node after the current head. Using the reference we had
kept, we will now delete the node using appropriate programming syntax.
Deletion
Deletion
• Deletion from the middle
• The most commonly used technique also utilizes two pointers. Similar to
insertion, we find the index we want to delete from and traverse till we have
found the node. Later, we perform some pointer manipulations and delete
the node.
• After we have reached the position of the said node, we will set its pointers to
the pointer of the node ahead of it. An example is shown in the next slide.
Deletion
Deletion
• Deletion from the tail
• This follows from deletion from the middle. In this case, we simply delete the
final node and set the pre-final node’s pointer to NULL.
Other flavours of Linked Lists
• Generally, we use other, more powerful flavours of linked lists.
• A doubly linked list has links going in both directions instead of just
one! That means that we can traverse our linked list in both
directions!
• A circular linked list links the “last” element with the “first” of a singly
linked list. This means that our list will have no end now unless it is
empty. This is of special advantage if we want to traverse our linked
list easily.
• A doubly circular linked list mixes the best of both worlds!
Linked Lists

Arrays and Linked Lists

Uploaded by

Copyright:

Available Formats

Arrays and Linked Lists

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Arrays and Linked Lists

Uploaded by

Copyright:

Available Formats

Arrays and Linked

A comparative study of these interrelated data structures

• Deleting the last element

• Insertion in the head

You might also like