Scribd
Upload
8 views48 pages

Data Structures and Algorithms Week 2

The document provides an overview of linked lists, highlighting their advantages over arrays, such as efficient insertion and deletion operations. It details the different types of linked lists (singly, doubly, and circular) and explains basic operations like traversal, finding the lowest value, deleting, inserting, and modifying nodes. The content emphasizes the importance of managing pointers to maintain the integrity of the linked list during these operations.

Uploaded by

wild.butcute19
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
8 views48 pages

Data Structures and Algorithms Week 2

The document provides an overview of linked lists, highlighting their advantages over arrays, such as efficient insertion and deletion operations. It details the different types of linked lists (singly, doubly, and circular) and explains basic operations like traversal, finding the lowest value, deleting, inserting, and modifying nodes. The content emphasizes the importance of managing pointers to maintain the integrity of the linked list during these operations.

Uploaded by

wild.butcute19
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 48

LINKED LIST

LINKED LIST DATA


STRUCTURE

Linked list data structure mainly allows


efficient insertion and deletion
operations compared to arrays. Like
arrays, it is also used to implement other
data structures like stack, queue and
deque.
LINKED LIST VS. ARRAYS
LINKED LIST ARRAYS
Data Structure: Non- Data
contiguous Structure: Contiguous

Memory Memory
Allocation: Typically Allocation: Typically
allocated one by one to allocated to the whole array
individual elements
Insertion/ Insertion/
Deletion: Efficient Deletion: Inefficient

Access: Sequential Access: Random


TYPES OF
LINKED LIST
1. Singly Linked List - is the simplest type
of linked list in which every node contains
some data and a pointer to the next node of
the same data type.
Marksman Marksman Marksman
0 1 2
Lesl Marksma Beat Marksma Miya NUL
ey n1 rix n2
L
2. Doubly Linked List - is a more complex
type of linked list that contains a pointer to
the next as well as the previous node in
sequence.
7 5
3
NUL Gor Atla Lin NUL
5 7 3 5
L d s g L
3. Circular Linked List - is a type of linked
list in which the last node’s next pointer
points back to the first node of the list,
creating a circular structure. This design
allows for continuous traversal of the list, as
1 2
there is 3no null to end the list.
Odet Phar Vale 1
2 3
te sa
BASIC
OPERATIONS
OF LINKED LIST
TRAVERSAL OF A LINKED
LIST
Traversing a linked list means to go through the
linked list by following the links from one node to
the next.

Traversal of linked lists is typically done to search


for a specific node, and read or modify the node's
content, remove the node, or insert a node right
before or after that node.

To traverse a singly linked list, we start with the


first node in the list, the head node, and follow that
TRAVERSAL OF A LINKED
LIST

Marksman Marksman Marksman


0 1 2
Lesl Marksma Beat Marksma Miya NUL
ey n1
rix n2
L
TRAVERSAL OF A LINKED
LIST

Marksman Marksman Marksman


0 1 2
Lesl Marksma Beat Marksma Miya NUL
ey n1
rix n2
L
TRAVERSAL OF A LINKED
LIST

Marksman Marksman Marksman


0 1 2
Lesl Marksma Beat Marksma Miya NUL
ey n1
rix n2
L
TRAVERSAL OF A LINKED
LIST

Marksman Marksman Marksman


0 1 2
Lesl Marksma Beat Marksma Miya NUL
ey n1
rix n2
L
TRAVERSAL OF A LINKED
LIST

Marksman Marksman Marksman


0 1 2
Lesl Marksma Beat Marksma Miya NUL
ey n1
rix n2
L
TRAVERSAL OF A LINKED
LIST

Marksman Marksman Marksman


0 1 2
Lesl Marksma Beat Marksma Miya NUL
ey n1
rix n2
L
FIND THE LOWEST VALUE IN A LINKED
LIST

To find the lowest value we need


to traverse the list. But in addition
to traversing the list, we must
also update the current lowest
value when we find a node with a
lower value.
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 30
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 30
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 5
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 5
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 2
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 2
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 2
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 2
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest value: 1
FIND THE LOWEST VALUE IN A LINKED
LIST

00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
Lowest
value: 1
DELETE A NODE IN A LINKED LIST
In this case we have the link (or pointer or
address) to a node that we want to delete.

It is important to connect the nodes on each side


of the node before deleting it, so that the linked list
is not broken.

So before deleting the node, we need to get the


next pointer from the previous node, and connect
the previous node to the new next node before
deleting the node in between.
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
DELETE A NODE IN A LINKED LIST
00 01 02 04

30 01 5 02 2 04 1 NUL
L
INSERT A NODE IN A LINKED
LIST
Inserting a node into a linked list is very similar to
deleting a node, because in both cases we need to
take care of the next pointers to make sure we do
not break the linked list.

To insert a node in a linked list we first need to


create the node, and then at the position where we
insert it, we need to adjust the pointers so that the
previous node points to the new node, and the new
node points to the correct next node.
INSERT A NODE IN A LINKED LIST
00 01 02 04

30 01 5 02 2 04 1 NUL
L
INSERT A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
MODIFY A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
MODIFY A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
MODIFY A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
MODIFY A NODE IN A LINKED LIST
00 01 02 03
04
30 01 5 02 2 03 3 04
1 NUL
L
5
MODIFY A NODE IN A LINKED LIST
00 01 02 03
04
30 01 2 02
2 03 3 04
1 NUL
L
0 5

You might also like