Data Structure

Week 1- Introduction

Assoc. Prof. Dr. Kürşat Mustafa KARAOĞLAN

2025- Fall
Course logistics in brief
Instructor : Assoc. Prof. Dr. Kürşat Mustafa Karaoğlan,
kkaraoglan@karabuk.edu.tr
Course Lab. Assistant : Res. Asst. Saliha ÖZGÜNGÖR,
salihaozgungor@karabuk.edu.tr
Time : Check out your system
Course Materials : • Çölkesen, Rıfat, Veri Yapıları ve Algoritmalar, 7. Basım,
Papatya Yayınevi.
• Cormen, Thomas H., et al. Introduction to Algorithms. 4th
ed., MIT Press, 2022.
• Horowitz, Ellis, Sartaj Sahni, and Susan Anderson-Freed.
Fundamentals of Data Structures in C. 2nd ed., Silicon
Press, 2008.
• Tenenbaum, Aaron M., et al. Data Structures Using C.
Prentice Hall, 1990.

Office Hours : Friday 11:00 p.m.-12:00 p.m.

Introduction to Data structures
• A data structure constitutes a systematic methodology for the organization, storage, and
management of data elements within computational memory systems, designed to facilitate
optimal retrieval and manipulation operations. This organizational paradigm serves as the
foundational abstraction layer between raw data representation and algorithmic processing.
• Formally, a data structure can be defined as a collection of data elements whose
organization is characterized by specific relationships and constraints that govern data
access patterns, storage allocation, and operational complexity.
• These structures implement abstract data types through concrete computational
representations that map logical data relationships to physical memory configurations.
Structural Design Principles
• The efficacy of data structure implementation is governed by two fundamental design
criteria:
1. Representational Fidelity: The structural organization must maintain sufficient
complexity to accurately model the semantic relationships and constraints inherent in the
problem domain. This ensures that the abstract data relationships correspond
meaningfully to real-world entity associations and dependencies.
2. Computational Efficiency: The structural implementation must maintain algorithmic
simplicity to enable efficient data processing operations. This principle encompasses both
time complexity considerations (operational performance) and space complexity
constraints (memory utilization optimization).
Classification and Characteristics (1)
• Data structures can be taxonomically classified based on various characteristics including
linearity (linear vs. non-linear), mutability (static vs. dynamic), and access patterns
(sequential vs. random access). Each classification exhibits distinct performance
characteristics for fundamental operations including insertion, deletion, traversal, and
search operations.
• The selection of appropriate data structures represents a critical design decision that
directly impacts system performance, memory utilization, and algorithmic complexity,
requiring careful consideration of the specific computational requirements and operational
constraints of the target application domain.

<The data structure can be sub-divided into major types>

Linear Data Structure , Non-linear Data Structure
Classification and Characteristics (2)
Linear Data Structures
• Definition: A data structure is classified as linear when its elements are
organized in a sequence or linear list format.
• Characteristics:
• Data elements are arranged in a linear (sequential) manner
• Physical storage in memory does not need to be sequential
• Each element has a relationship with its predecessor and successor
• Elements are accessed in a sequential order
• Examples of Linear Data Structures:
• Arrays
• Linked Lists
• Stacks
• Queues
• *Hash Tables

*Hash tables are neither completely linear nor completely non-linear in a strict sense. They exhibit a hybrid
structure and are often treated as a special category.
Non-Linear Data Structures
• Definition: A data structure is classified as non-
linear when data elements are not arranged in a
sequential manner.
• Characteristics:
• Data elements do not follow a linear sequence
• Insertion and deletion operations cannot be performed in
a linear fashion
• Elements may have hierarchical or network-like
relationships
• Multiple paths may exist between elements
• Examples of Non-Linear Data Structures:
• Trees
• Graphs
• Heaps (Heap is a special type of tree.)
• Hash Tables (hybrid)- No Sequential Relationship,
Random Access Pattern, Collision Handling

* Heap is a tree, but not every tree is a heap.

Contents (1)
• Graph Data Structure: A graph is a data structure where data elements maintain
relationships between pairs of elements that do not necessarily follow a hierarchical
structure.
• Characteristics:
• Elements can be connected to multiple other elements
• Relationships are not bound by hierarchical constraints
• Can represent complex networks and connections
• Allows for non-linear relationships between data elements
• Key Features:
• Vertices/Nodes: Individual data elements
• Edges: Connections between vertices
• Non-hierarchical: Unlike trees, no parent-child restrictions
• Flexible relationships: Any vertex can connect to any other vertex
 Contents (2)
• Tree Data Structure: A tree is a data structure that reflects hierarchical relationships among various
elements, also known as a rooted tree graph.
• Characteristics:
• Data contains hierarchical relationships between elements
• Follows a parent-child structure
• Has a single root node at the top level
• Each node (except root) has exactly one parent
• Nodes can have multiple children
• Key Features:
• Root: Top-level node with no parent
• Parent-Child relationship: Clear hierarchical connections
• Leaves: Nodes with no children
• Branches: Paths from root to leaves
Contents (2) cont.
• Files can be maintained using arrays, but
records with both group items and
elementary items are best represented using
tree structures. An employee personnel
record illustrates this concept well,
containing data items like Social Security
Number, Name, Address, Age, Salary, and
Dependents.
• The hierarchical nature becomes evident
when examining group items. Name serves as
a group item containing subitems Last, First,
and MI (middle initial). Address is also a group
item with Street address and Area address
subitems, where Area address further breaks
down into City, State, and ZIP code
number.This creates a natural tree structure
with the main employee record as the root,
group items (Name, Address) as branches,
and elementary items (Last, First, City, State,
etc.) as leaves. The hierarchical organization
provides clear data relationships, efficient
access patterns, and scalable design for
complex record structures, making it
fundamental for database design and data
modeling where nested information needs
organized storage and retrieval.
 Contents (3)
• Array Data Structure: An array is a container data structure that can hold
a fixed number of items, where all items must be of the same data type.
• Fundamental Properties:
• Fixed size: Predetermined number of elements
• Homogeneous: All elements must be of the same type
• Foundation: Used by most other data structures to implement their algorithms
• Important Array Terminology
• Element: Each individual item stored within an array
• Represents the actual data value
• All elements share the same data type
• Index: The numerical position identifier for each element location in an array
• Used to access and identify specific elements
• Typically starts from 0 in most programming languages
• Enables direct access to array elements

*Array is particularly useful when we

are dealing with lot of variables of the
same type.
Array Basic Operations
• Arrays support several fundamental operations that enable efficient data manipulation and
access.
• The basic operations include Traverse (printing all array elements one by one), Insertion (adding
an element at a specified index), Deletion (removing an element from a given index), Search
(finding an element using index or value), and Update (modifying an element at a specific index).
These operations form the foundation for working with array data structures in programming.
• When an array is initialized with a specific size in C language, the system automatically assigns
default values to its elements based on their data types. This initialization ensures that arrays
contain predictable values rather than random memory content, providing a consistent starting
point for data manipulation.
Insertion Operation
• Insert operation involves adding one or more data
elements into an array at specified positions. Based on
programming requirements, new elements can be
inserted at the beginning, end, or any given index of the
array. This flexibility allows developers to modify array
contents dynamically according to application needs.
• Insertion at the beginning requires shifting all existing
elements one position to the right, making it a costly
operation with O(n) time complexity. Insertion at the end
is the most efficient approach when the array has
available space, requiring only O(1) time complexity.
Insertion at a specific index involves shifting elements
from that position onwards to create space for the new
element
HW1: Insertion, Deletion and, Search Operations
 Contents (4)
• Linked List Structure: A linked list is a linear data structure where elements are stored in
nodes, and each node contains data and a reference (or pointer) to the next node in the
sequence. Unlike arrays, linked list elements are not stored in contiguous memory locations.
• Basic Structure: Each node in a linked list consists of two components:
• Data: The actual information stored in the node
• Next/Link: A pointer/reference to the next node in the sequence

Types of Linked Lists:

1. Singly Linked List
Key Characteristics: •Each node points to the next node
•Dynamic size: Can grow or shrink during runtime •Traversal possible in only one direction (forward)
•Non-contiguous memory: Nodes can be scattered •Last node points to NULL
throughout memory 2. Doubly Linked List
•Sequential access: Elements must be accessed •Each node has two pointers: next and previous
•Bidirectional traversal possible
sequentially from the head
•More memory overhead due to extra pointer
•No random access: Cannot directly access 3. Circular Linked List
elements by index like arrays •Last node points back to the first node
•Forms a circular chain
•No NULL pointer at the end
Linked List vs Array Comparison

Note: Linked lists are particularly useful when the size of data is unknown beforehand and frequent
insertions/deletions are required at the beginning of the structure.
 Contents (Stack, Queue, and Graph Data Structures)
• Stack (a) is a linear data structure that operates on the LIFO (Last In, First
Out) principle, meaning the last element added to the stack is the first one to
be removed. This behavior is similar to a stack of plates where you can only
add or remove plates from the top. The LIFO principle ensures that the most
recently inserted element is always the first to be accessed. Key operations
include push (adding elements to the top), pop (removing elements from the
top), peek (viewing the top element without removing it), and isEmpty
(checking if the stack is empty). Stacks are commonly used in function call
management, expression evaluation, undo operations in software
applications, and browser back button functionality.
• Queue (b) is another linear data structure that follows the FIFO (First In, First
Out) principle, where the first element added is the first one to be removed.
This resembles people waiting in a line at a bank or store, where the first
person in line is served first. The FIFO principle ensures fair and orderly
processing of elements in the sequence they were added. Primary operations
include enqueue (adding elements to the rear), dequeue (removing elements
from the front), front (viewing the front element), and isEmpty (checking if the
queue is empty). Queues are essential in process scheduling, print job
management, breadth-first search algorithms, and handling requests in web
servers.
• Graph (c) is a non-linear data structure consisting of vertices (nodes)
connected by edges, representing complex relationships between data
elements without hierarchical constraints. Unlike trees, graphs allow any
vertex to connect to any other vertex, creating flexible network structures.
Graphs can be directed (edges have specific directions) or undirected
(bidirectional connections), and weighted (edges have associated costs) or
unweighted (all connections are equal). This versatility makes graphs perfect
for modeling social networks, GPS navigation systems, computer networks,
and recommendation systems where relationships between entities are not
strictly hierarchical.
Stack Representation
• A stack can be implemented using various data structures including arrays, structures, pointers,
and linked lists. Stack implementations can be either fixed size (static) or dynamic resizing
(expandable). In this context, we focus on array-based stack implementation, which creates a fixed-
size stack with predetermined capacity limits.
• Stack operations typically involve initializing the stack structure, utilizing it for data storage and
retrieval, and de-initializing it when no longer needed. Beyond these foundational processes, stacks
primarily support two essential operations that define their LIFO (Last In, First Out) behavior.
• Push operation involves storing an element onto the stack by placing it at the top position. This operation adds new data to
the stack's uppermost location, making it the most recently added element.
• Pop operation removes and accesses the topmost element from the stack, following the LIFO principle where the last
pushed element becomes the first to be removed.
• Efficient stack utilization requires status monitoring capabilities to prevent overflow and underflow
conditions.
• Peek operation retrieves the top data element without removing it from the stack, allowing examination of the most recent
element while preserving stack integrity.
• isFull operation checks whether the stack has reached its maximum capacity, preventing overflow errors during push
operations.
• isEmpty operation determines if the stack contains any elements, preventing underflow errors during pop operations.
• Stack implementations maintain a top pointer that continuously references the last pushed data
element on the stack. This pointer represents the current top position and enables efficient access
to the uppermost element without traversal. The top pointer facilitates quick retrieval of the stack's
top value while maintaining the element's position within the structure, supporting both peek and pop
operations effectively.
 Sparse Matrix and its representations

• A matrix is a two-dimensional data object made of m rows and n

columns, therefore having total m x n values. If most of the
elements of the matrix have 0 value, then it is called a sparse
matrix.
Why to use Sparse Matrix instead of simple matrix ?
• Storage: There are lesser non-zero elements than zeros and thus
lesser memory can be used to store only those elements.
• Computing time: Computing time can be saved by logically
designing a data structure traversing only non-zero elements..

Time Complexity: O(m × n)

Memory savings: Only 6 elements are stored instead of 20

Processing efficiency: No operations with zero values
Storage optimisation: Dramatic space savings on large
sparse matrices
References

• Çölkesen, Rıfat, Veri Yapıları ve Algoritmalar, 7. Basım, Papatya Yayınevi.

• Cormen, Thomas H., et al. Introduction to Algorithms. 4th ed., MIT Press, 2022.
• Horowitz, Ellis, et al. Fundamentals of Data Structures in C. 2nd ed., Silicon Press, 2008.
• Tenenbaum, Aaron M., et al. Data Structures Using C. Prentice Hall, 1990.
• Lipschutz, Seymour. Data Structures with C. Schaum's Outlines, Tata McGraw-Hill Education Private Limited, 2011.
• Mohapatra, Subasish. Data Structures Using "C": Lecture Notes. Department of Computer Science and
Application, College of Engineering and Technology, Biju Patnaik University of Technology, n.d.
• GeeksforGeeks. Data Structures. www.geeksforgeeks.org/data-structures/
• MIT OpenCourseWare. Introduction to Algorithms (6.006). ocw.mit.edu
• Skiena, Steven S. The Algorithm Design Manual. 3rd ed., Springer, 2020.