BSIT Survival Kit

Module 3: Arrays and Linked Lists

Array Concepts

An array stores a fixed number of elements under one name. In most programming languages, all array elements must have the same data type.

Important terms:

Term	Meaning
Element	A value stored inside an array.
Index	A numeric position used to access an element.

In many languages, array indexes start at 0. For example, if an array has five fruits:

fruits = ["Apple", "Papaya", "Atis", "Santol", "Mango"]

Then:

fruits[0] = "Apple"
fruits[4] = "Mango"

Basic Array Operations

Operation	Description
Traverse	Visit or display each element one by one.
Insert	Add a new element at a chosen position.
Delete	Remove an element from a chosen position.
Search	Find an element by index or value.
Update	Change the value stored at an index.

One-Dimensional and Two-Dimensional Arrays

A one-dimensional array is like a single row of values.

scores[0], scores[1], scores[2], ...

A two-dimensional array is arranged using rows and columns, like a table.

matrix[row][column]

Arrays: Strengths and Limitations

Arrays are easy to use because each item can be accessed directly by index. This makes reading an element fast.

However, insertion and deletion can be expensive when they happen in the middle of an array. Elements may need to shift left or right to keep the array organized.

For searching:

an unsorted array may require checking each element one by one
a sorted array can support faster searching, such as binary search

Linked List Concepts

A linked list stores data as nodes. Each node contains:

the data item
a link or reference to the next node

Unlike arrays, linked lists do not require all elements to be stored beside each other in memory. This allows them to grow or shrink while the program runs.

Linked List Strengths and Limitations

Strength	Limitation
Can grow dynamically.	No direct access by index.
Insertions and deletions can be efficient when the correct node is known.	Searching may require following links from the beginning.
Memory is allocated as needed.	Extra memory is needed for links/references.

Common Linked List Variations

Type	Description
Singly linked list	Each node points to the next node.
Circular linked list	The last node points back to the first node.
Doubly linked list	Each node points to both the previous and next node.
Doubly circular linked list	A doubly linked list where the last and first nodes are also connected.

Diagram Descriptions

A simple linked list may be shown as circles or boxes connected by arrows. Each circle/box represents a node, and each arrow represents the link to the next node.

A dummy node is an extra node used to simplify operations near the beginning or end of a list. It may act as a placeholder so that insertion and deletion logic becomes more consistent.