Linked List

An array is a very useful data structure provided in programming languages. However, it has at least two
limitations:
 its size must be known at compilation time and
 the data in the array are separated in computer memory by the same distance, which means that inserting
an item inside the array requires shifting other data in this array.

This limitation can be overcome by using linked structures.

A linked structure is a collection of nodes storing data and links to other nodes. In this way, nodes can be
located anywhere in memory, and passing from one node of the linked structure to another is accomplished
by storing the addresses of other nodes in the linked structure. Although linked structures can be
implemented in a variety of ways, the most flexible implementation is by using pointers.

1 3 7 2
 Linked List
If a node contains a data member that is a pointer to another node, then many nodes can be put together
using only one variable to access the entire sequence of nodes. Such a sequence of nodes is the most
frequently used implementation of a linked list, which is a data structure composed of nodes, each node
holding some information and a pointer to another node in the list.

If a node has a link only to its successor in this sequence, the list is called a singly linked list.

Each node in the list is an instance of the following class definition:

struct ListNode
data {
int data;
next struct ListNode
*next;
};
A node includes two data members: data and next. The data member is used to store information, and
this member is important to the user. The next member is used to link nodes to form a linked list. It is an
auxiliary data member used to maintain the linked list. Note that ListNode is defined in terms of itself
because one data member, next, is a pointer to a node of the same type that is just being defined.
Structures that include such a data member are called self-referential objects.
 Linked List
One way to create this three-node linked list is to first generate the node for number 10, then the node for
15, and finally the node for 30. Each node has to be initialized properly and incorporated into the list.
Create the first node on the list and make the variable p a pointer to this node:

struct ListNode *p =
(struct ListNode *)malloc(sizeof(struct ListNode));
p->data = 10;
p->next = NULL;

This done in four steps: p 10

 Create a new node p;
 The data member of this node is set to 10;
null
 the node’s next member is set to null;
 make p a pointer to the newly created node.
 Linked List
The second node is created with the assignment:

p->next = (struct ListNode *)malloc(sizeof(struct ListNode));

p->next->data = 15;
p->next->next = NULL;

Here p->next is the next member of the node pointed to by p. Note that the data members of nodes
pointed to by p are accessed using the arrow notation, which is clearer than using a dot notation, as in
(*p).next.

p 10 15

null
 Linked List
The linked list is now extended by adding a third node with the assignment

p->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));

p->next->next->data = 30;
p->next->next->next = NULL;

Here p->next->next is the next member of the second node. This cumbersome notation has to be
used because the list is accessible only through the variable p.

p 10 15 30

null

Our linked list example illustrates a certain inconvenience in using pointers: the longer the linked list, the
longer the chain of nexts to access the nodes at the end of the list. In this example, p->next->next-
>next allows us to access the next member of the 3rd node on the list. But what if it were the 103 rd or,
worse, the 1,003rd node on the list?
Therefore, other ways of accessing nodes in linked lists are needed.
 Linked List
One way is always to keep two pointers to the linked list: one to the first node and one to the last:

head 10 15 30

null
tail

The singly linked list implementation uses structure LinkedList that defines head and tail, which are
pointers to the first and the last nodes of a list.

struct LinkedList
{
struct ListNode *head, *tail;
};
 Linked List
Function Empty checks if a linked list a is empty.

int Empty(struct LinkedList *a)

{
return a->head == NULL;
}

The list is declared with the statement:

struct LinkedList *list =

(struct LinkedList *) malloc(sizeof(struct LinkedList));

Besides the head and tail members, we’ll define functions that allow us to manipulate the lists.

We now look more closely at some basic operations on linked lists.

 AddFirst: insert to the start
Adding a node at the beginning of a linked list is performed in three steps:

1. An empty node temp is created. The node’s info member is initialized to a particular integer.

struct ListNode *temp =

(struct ListNode *)malloc(sizeof(struct ListNode));
temp->data = val;
temp->next = NULL;

head tail

temp 5 10 15 30

null null
 AddFirst: insert to the start
2. Because the node is being included at the front of the list, the next member becomes a pointer to the
first node on the list; that is, the current value of head.

temp->next = head;

head tail

temp 5 10 15 30

null
 AddFirst: insert to the start
3. The new node precedes all the nodes in the list, but this fact has to be reflected in the value of head;
otherwise, the new node is not accessible. Therefore, head is updated to become the pointer to the new node.

head = temp;

head tail

temp 5 10 15 30

null
 AddFirst: insert to the start
void addFirst(struct LinkedList *a, int val)
{
if (a->tail == NULL) // list is empty
{
a->head = a->tail =
(struct ListNode *)malloc(sizeof(struct ListNode));
a->head->data = val;
a->head->next = NULL;
}
else
{
struct ListNode *temp =
(struct ListNode *)malloc(sizeof(struct ListNode));
temp->data = val;
temp->next = a->head;
a->head = temp;
}
}
 AddLast: insert to the end
The process of adding a new node to the end of the list has three steps.

1. An empty node is created.

tail->next = (struct ListNode *)malloc(sizeof(struct ListNode));

head tail

10 15 30 ?

?
 AddLast: insert to the end
2. Move pointer tail to the new node.

tail = tail->next;

head tail

10 15 30 ?

?
 AddLast: insert to the end
3. Fill the data for the last node.

tail->data = val;
tail->next = NULL;

head tail

10 15 30 40

null
 AddLast: insert to the end
void addLast(struct LinkedList *a, int val)
{
if (a->tail != NULL) // list is not empty
{
a->tail->next = (struct ListNode *)malloc(sizeof(struct ListNode));
a->tail = a->tail->next;
a->tail->data = val;
a->tail->next = NULL;
}
else
{
a->head = a->tail =
(struct ListNode *)malloc(sizeof(struct ListNode));
a->head->data = val;
a->head->next = NULL;
}
}
 RemoveFirst: delete from the start
Function removeFirst returns 1 is deletion is successful, otherwise 0. There are two special cases to
consider:
 One case is when we attempt to remove a node from an empty linked list. If such an attempt is made, the
program is very likely to crash, which we don’t want to happen. So, in this case we do nothing, but
simply return 0.
 The second special case is when the list has only one node to be removed. In this case, the list becomes
empty, which requires setting tail and head to null.

head tail

10 15 30 40

null
 RemoveFirst: delete from the start
Move the head pointer one position forward.

head = head->next;

head tail

10 15 30 40

null
 RemoveFirst: delete from the start
int removeFirst(struct LinkedList *a)
{
if (Empty(a)) return 0;
if (a->head == a->tail) // only one node in a list
a->head = a->tail = NULL;
else
{
struct ListNode *temp = a->head;
a->head = a->head->next;
free(temp);
}
return 1;
}
 RemoveLast: delete from the end
Now consider the process of deleting a node from the end of the list. It is implemented as the function
removeLast().

The problem is that after removing a node, tail should refer to the new tail of the list; that is, tail must be
moved backward by one node. But moving backward is impossible because there is no direct link from the
last node to its predecessor. Hence, this predecessor must be found by searching from the beginning of the
list and stopping right before tail. This is accomplished with a temporary variable temp that scans the list
within the for loop. The variable temp is initialized to the head of the list, and then in each iteration of the
loop it is advanced to the next node.

In removing the last node, the two special cases are the same as in removeFirst():
 If the list is empty, then nothing can be removed;
 When a single-node list becomes empty after removing its only node, which also requires setting head
and tail to null.
 RemoveLast: delete from the end
Consider the list, where temp first refers to the head node holding number 5.

temp = head;

head tail

temp 5 10 15 30 40

null
 RemoveLast: delete from the end
Move temp forward until it will point to the node next to the last.

while(temp->next != tail) temp = temp->next;

head temp tail

5 10 15 30 40

null
 RemoveLast: delete from the end
The last node is deleted.

tail = temp; tail->next = null;

head temp tail

5 10 15 30 40

null nill

The most time-consuming part of removeLast() is finding the next to last node performed by the
for loop. It is clear that the loop performs n – 1 iterations in a list of n nodes, which is the main
reason this member function takes O(n) time to delete the last node.
 RemoveLast: delete from the end
int removeLast(struct LinkedList *a)
{
if (Empty(a)) return 0;
if (a->head == a->tail) // only one node in a list
{
a->head = a->tail = NULL;
}
else // if more than one node in the list
{
struct ListNode *temp = a->head;
// find the predecessor of tail
while (temp->next != a->tail) temp = temp->next;
a->tail = temp; // the predecessor of tail becomes tail
free(a->tail->next);
a->tail->next = NULL;
}
return 1;
}
 9898. Linked List Sum

Given a linked list, find the sum of its elements.

struct ListNode
{
int val;
struct ListNode *next;
};

Implement function sum that finds the sum of linked list elements.

int sum(ListNode *head)

head 1 2 3

The sum of elements of a linked list is 6.

 9898. Linked List Sum

Compute the sum of the list elements in the res variable.

int sum(ListNode *head)

{
int res = 0;

Move forward through the list until head becomes NULL.

Add to res the current value of the list element head->val.

while (head != NULL)

{
res += head->val;
head = head->next;
}
return res;
}
 9899. Linked List Length

Given a linked list, find the length of the linked list.

struct ListNode
{
int val; Iterate the linked list from head to tail
struct ListNode *next; and count the number of elements.
};

Implement function length that finds the length of the linked list.

int length(ListNode *head)

head 1 2 3

The length of the linked list is 3.

 10042. Linked List Cycle

Given a linked list. Does it contain a cycle?

head 1 2 3
struct ListNode
{
Function hasCycle returns 0 because
int val;
this linked list does not contain a cycle.
struct ListNode *next;
};

Implement a function hasCycle that returns 1 if linked list contains a cycle and 0 otherwise.

int hasCycle(ListNode *head)

head 1 2 3 4 5

Function hasCycle returns 1 because this linked list contains a cycle.

 10042. Linked List Cycle
p, q
We’ll use two pointers p and q, moving them
according to the principle of baby step giant step. 1 2 3 4 5 Initialization

First, assign them to the start of the list. Next, p q

iteratively move the first pointer p forward one

1 2 3 4 5 iteration 1
position in the list, and the second pointer q move
two positions forward in the list. We stop if: p q
 one of the pointers (this will be the pointer q)
has reached the end of the list. Then the list has 1 2 3 4 5 iteration 2
no cycle.
 both pointers point to one element. This means p, q

that the fast pointer q caught the slow pointer p,

1 2 3 4 5 iteration 3
and the list contains a cycle.
 10042. Linked List Cycle

int hasCycle(ListNode *head)

{
if (head == NULL) return 0;

ListNode* p = head; Set up the pointers p and q to the start of the list.
ListNode* q = head;

while (q->next && q->next->next) While there are at least two elements behind the q
{ pointer (the fast pointer can be moved two steps
p = p->next; forward), we continue the loop.
q = q->next->next;
If pointers are equal, they point to the same
if (p == q) return 1; memory location. The fast pointer q caught up the
} slow p, the list contains a cycle.
return 0;
There is no cycle, return 0.
}
 10043. Linked List Cycle starting point

Given a linked list. Return pointer to the node where cycle starts. If there is no cycle, return null.

struct ListNode head 1 2 3

{
int val; Function detectCycle returns null becau
struct ListNode *next; se this linked list does not contain a
}; cycle.

Implement a function detectCycle that returns a pointer to the node where cycle starts. If there is no
cycle, return null.

ListNode* detectCycle(ListNode *head)

head 1 2 3 4 5

Function detectCycle returns pointer to the node with value 3,

the starting point of the cycle.
 10043. Linked List Cycle starting point

Using two pointers (slow and fast), we determine whether the linked list contains a loop. Let the list
contains a loop, and p points to the vertex where the fast pointer meets with the slow one. Set q to the start
of the list.
x
Let the distance from the start to the vertex where the cycle starts is x.
The distance from the start of the loop to the meeting point of two
pointers is y. The distance from the vertex pointed to by p to the y
beginning of the cycle along the list is z.
q
Suppose the pointers have met so that the fast pointer has only gone
z p
one round of the cycle. That is, the slow one went the path x + y, and
the fast one x + y + z + y. Considering that a fast pointer is twice as fast
as a slow one, we get an equality:
2 (x + y) = x + y + z + y or x = z

This means that now it is enough to iteratively move the pointers p and q step by step until they become
equal (will point to the same memory location). Moreover, this will definitely happen at the node, which is
the beginning of the cycle.