Data Structure and Algorithm Lesson 2

ADVANCED DATA
STRUCTURES
Arrays Trees
Linked Lists Heaps
Stacks Hash tables
Queues Graphs
Introduction to Arrays
An array is a collection of items of the same variable type
that are stored at contiguous memory locations.
2
Basic Terminologies of Array
Array Index:
In an array, elements are identified by
their indexes. Array index starts from
0.
Array element:
Elements are items stored in an array
and can be accessed by their index.
Array Length:
The length of an array is determined by
the number of elements it can contain.
Linked Lists
A linked list is a linear data structure
consisting of a sequence of elements
called nodes, where each node
contains both the data and a reference
(or pointer) to the next node in the
sequence.
5
Types of Linked Lists
There are several types of linked lists, but the two
most common ones are:
1.Singly Linked List: In this type of linked list, each
node contains data and a pointer to the next node in
the sequence. The last node points to null, indicating
the end of the list.
2.Doubly Linked List: Each node in a doubly linked
list contains data, a pointer to the next node, and a
pointer to the previous node. This allows for traversal
in both directions. 6
OPERATIONS ON LINKED LISTS:
1.Insertion: Adding a new node to the
list.
2.Deletion: Removing a node from the
list.
3.Traversal: Iterating through the list to
access or manipulate its elements.
4.Search: Finding a specific element
within the list.
5.Concatenation: Combining two linked
lists into one.
7
Insertion:
Example: Suppose we have a singly linked list with nodes containing
integers. To insert a new node with the value 10 at the end of the list:
Original Linked List: 1 -> 2 -> 3 -> NULL

After Insertion: 1 -> 2 -> 3 -> 10 -> NULL
Deletion:
•Example: Continuing from the previous example, if we want to remove
the node containing the value 2 from the list:
Original Linked List: 1 -> 2 -> 3 -> 10 -> NULL

After Deletion: 1 -> 3 -> 10 -> NULL
Traversal:
Example: Suppose we have the following singly linked list with characters
representing a string. Traversing the list would mean iterating through
each node and printing its value:
Linked List: 'H' -> 'e' -> 'l' -> 'l' -> 'o' -> NULL
Traversal Output: Hello
Search:
Example: Consider the same linked list from the traversal example. If we
want to search for the character 'l' in the list:
Linked List: 'H' -> 'e' -> 'l' -> 'l' -> 'o' -> NULL
Search for 'l': Found at index 2 and 3
Concatenation:
Example: Suppose we have two singly linked lists, list1 and list2, with the
following elements:
list1: 1 -> 2 -> 3 -> NULL

list2: 4 -> 5 -> 6 -> NULL
Concatenating list2 to the end of list1 would result in:
Concatenated List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Applications of Linked Lists
•Dynamic Memory Allocation: Linked lists are commonly used
in dynamic memory allocation systems, such as malloc() and
free() in C.
•Implementation of Stacks and Queues: Linked lists serve as
the underlying data structure for implementing stacks (using
singly linked lists) and queues (using either singly or doubly
linked lists).
•Polynomial Manipulation: Linked lists can be used to
represent and manipulate polynomials in mathematical
computations.
•Sparse Matrix Representation: Linked lists are suitable for
representing sparse matrices efficiently. 13
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {

struct Node* newNode = malloc(sizeof(struct Node));
if (!newNode) {
printf("Memory allocation failed!\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
int main() {
struct Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
printf("Linked List: ");

for (struct Node* current = head; current != NULL; current = current->next)
printf("%d -> ", current->data);
printf("NULL\n");
for (struct Node* current = head; current != NULL;) {

struct Node* temp = current;
current = current->next;
free(temp);
}
return 0;
}
Stacks:
•Definition and properties of stacks (Last In First Out - LIFO).
•Implementation of stacks using arrays or linked lists.
•Operations on stacks (push, pop, peek).
•Applications of stacks in expression evaluation, function
calls, and backtracking algorithms.
16
Definition and Properties of Stacks
(Last In First Out - LIFO):
•A stack is a linear data structure that follows the

Last In First Out (LIFO) principle, meaning that the
last element added to the stack is the first one to be
removed.
•Stacks can be visualized as a collection of elements
arranged in a specific order where elements are
added and removed from the top (the end where
insertion and deletion occur).
17
Implementation of Stacks using Arrays or
Linked Lists:
•Stacks can be implemented using either arrays or
linked lists.
•Array-based Implementation: In this approach, a
fixed-size array is used to store stack elements. The
top of the stack is represented by a variable that
points to the index of the top element in the array.
•Linked List-based Implementation: In this approach,
a linked list is used to represent the stack.
18
Operations on Stacks (push, pop, peek):
•Push: Adds an element to the top of the stack.

•Pop: Removes the element from the top of the stack.
•Peek: Returns the element at the top of the stack
without removing it.
19
Applications of Stacks
•Expression Evaluation
•Function Calls
•Backtracking Algorithms
20

Data Structure and Algorithm Lesson 2

Uploaded by

Copyright:

Available Formats

Data Structure and Algorithm Lesson 2

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

Data Structure and Algorithm Lesson 2

Uploaded by

Copyright:

Available Formats

ADVANCED DATA

Original Linked List: 1 -> 2 -> 3 -> NULL

Original Linked List: 1 -> 2 -> 3 -> 10 -> NULL

list1: 1 -> 2 -> 3 -> NULL

Concatenating list2 to the end of list1 would result in:

Concatenated List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

struct Node* createNode(int data) {

printf("Linked List: ");

for (struct Node* current = head; current != NULL;) {

•A stack is a linear data structure that follows the

•Push: Adds an element to the top of the stack.

You might also like