Arrays vs. Linked Lists

LINKED
LISTS

A linked list is a linear collection of data elements whose order is not given by their
physical placement in memory. Instead, each element points to the next. It is a data
structure consisting of a collection of nodes which together represent a sequence.

Arrays vs. Linked Lists
Arrays can be used to store linear data of similar types, but arrays have the following
limitations.
1. The size of the arrays is fixed: So we must know the upper limit on the number of
elements in advance. Also, generally, the allocated memory is equal to the upper limit
irrespective of the usage.
2. Inserting a new element in an array of elements is expensive because the room has to
be created for the new elements and to create room existing elements have to be
shifted.

Advantages over arrays
1. Dynamic size
2. Ease of insertion/deletion

Drawbacks:
1. Random access is not allowed. We have to access elements sequentially starting from
the first node. So we cannot do binary search with linked lists efficiently with its default
implementation.
2. Extra memory space for a pointer is required with each element of the list.
3. Not cache friendly. Since array elements are contiguous locations, there is locality of
reference which is not there in case of linked lists.

IMPLEMENTATION
A linked list is represented by a pointer to the first node of the linked list. The first node is
called the head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1. data
2. Pointer (Or Reference) to the next node

#include <stdio.h>
#include <stdlib.h>
/*A struct is used because every node has the same properties: a data element
and a pointer to the next node in the linked list. */
struct Node {
int data; //the node stores an integer value
struct Node* next; //a pointer to the next node in the linked list
};
int main()
{
struct Node* head = NULL; //create a new node with a pointer to NULL
//a pointer to NULL means that the node is not connected to another node
// by convention, we name the first node “head”
struct Node* second = NULL;
struct Node* third = NULL;
head = (struct Node*)malloc(sizeof(struct Node));

/*the malloc function allocates memory to the node. In this case, we
allocate the amount of memory that the struct takes up, since every node will
use the struct, it will take up the same amount of space [sizeof(struct
Node)].
We also use a cast (struct Node*) to tell the processor that the pointer is a
pointer to a struct, not just any regular memory pointer */
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1; //set head to store the data element ‘1’

head->next = second; //head now points to the next node, “second”
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL; //As the last node in this list, third points to NULL
return 0;
}

LINKED LIST OPERATIONS
Much of linked list operations depend on pointer manipulation.

An empty node
NULL
head

A linked list
1 2 3 NULL
head second third

Removing a node from a linked list
When there is no pointer to a node, it automatically drops off the linked list. Therefore,
deleting a node is simply done by removing the pointer to it.
For, example to remove the second node in the list above, we move the head pointer to the
third node. Since there is nothing pointing to second, it is effectively removed from the list.
head->next = third;
1 3 NULL
head third

Inserting a new node into the list
At the end
1. Create the new node
struct Node* fourth = NULL;
fourth = (struct Node*)malloc(sizeof(struct Node));
fourth->data = 4;
2. Set the pointer of the last node to the new node
third->next = fourth;
1 2 3 4 NULL
head second third fourth
At the beginning
1. Create a new node
struct Node* newNode = NULL;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 0;
2. Set the pointer of the new node to the current head
newNode->next = head;
3. Make the new node the head of the list
head = newNode;
0 1 2 3 NULL

NOTE: We really only care about knowing where the linked list starts, or the “head” of the
list. Once we know the head, we can access any other node in the list.

Inserting between two nodes
We use the example of inserting a node, newNode, between the second and third nodes.
1. Create a new node
struct Node* newNode = NULL;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 0;
2. Set the pointer of the new node to the node it will precede
newNode->next = third;
3. Set the pointer of the node newNode will follow to point to newNode
second->next = newNode;
head second newNode third
1 2 0 3 NULL

LINKED LIST TRAVERSAL
We need a way to read the data stored in the linked list. Just as we would iterate through an
array using a for loop, we can iterate through a linked list. However, we use a while loop
because we need unbounded iteration. Recall that a linked list does not have any limit on
the number of elements it can store, as long as more memory can be allocated.
When we create an array, however, we know its exact size. This is not so for a linked list
and so we use a while loop that starts from the head of the list until it reaches the end.

How do we know when we have reached the end of a linked list?
Recall that the last node always points to NULL. So we iterate through the nodes in the
linked list until we reach a node that points to NULL.

/*This function takes a node pointer as an argument. Recall that once we know
where the head of the node is, we can find any other node. Using a node
pointer also gives us flexibility. For example, we can choose to print all
the elements starting from the second or third or any other node we desire.
*/
void printList(struct Node* n)
{
//unbounded iteration;In other words, while we have not reached the last node
while (n != NULL) {
printf(" %d ", n->data); //print the data inside the node
n = n->next; //move to the next node in the list
}
}
Suppose we call the function printList(head);

0 1 2 3 NULL
The printList function starts from the head of the linked list moving to the next node until it
reaches the fourth node. The data in fourth is printed and then we exit the loop because
fourth points to NULL.

Arrays vs. Linked Lists

Uploaded by

Copyright:

Available Formats

Arrays vs. Linked Lists

Uploaded by

Document Information

Original Title

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 vs. Linked Lists

Uploaded by

Copyright:

Available Formats

LINKED

head = (struct Node*)malloc(sizeof(struct Node));

head->data = 1; //set head to store the data element ‘1’

Suppose we call the function printList(head);

head second third fourth

You might also like