Computer Programming
Array Data Structure
Scope and Coverage
• What are Data Structures
• Common Data Structures
• Categories of Data Structures
• Array Data Structure
• The advantages and disadvantages of Array
data structure
Common data structures
Common data structures
What is data structure?
• A data structure is a way of organizing and storing
data
– so that it can be accessed and modified efficiently.
• The choice of data structure impacts the performance
of algorithms in terms of
– time complexity,
– memory usage,
– operations such as:
• searching,
• insertion,
• deletion.
Common data structures
Categories of data structures
Common data structures
• The data structures are categorized into two:
1) Linear Data Structures:
– arrays
– linked Lists
– stacks
– queues
2) Non-Linear Data Structures:
– trees
– hash map (dictionaries)
– graphs
Common data structures
1) Linear Data Structures
• Linear data structures organize data in a sequential
manner.
I. Array: Is the collection of elements of the same type
stored in a contiguous memory location.
• An array has a fixed size.
• Each data element is assigned a positive numerical
value called an Index.
– which corresponds to the position of that item in the array.
• Majority of languages define the starting index of the
array as 0.
Common data structures
1) Linear Data Structures
i. Arrays
• Example of a simple array of size 6
Common data structures
1) Linear Data Structures
i. Arrays
Basic array operations
• Insert: Inserts an element at a given index.
• Get: Returns the element at a given index.
• Delete: Deletes an element at a given index.
• Size: Gets the total number of elements in an array.
Common data structures
• The index value is used to access individual
elements of an array.
• There are two types of array:
– One Dimensional Array
– Multi Dimensional Array
Common data structures
Creating an array
• An array must be created using new operator
and with a specific size.
• The size must be an integer value but not
– a byte,
– short,
– long.
• The following syntax is used to create an array.
Common data structures
Creating one dimensional array
Common data structures
Creating one dimensional array
• An array can also be initialized at the time of its
declaration.
• When an array is initialized at the time of its
declaration,
– it does not require to specify the size of the array and
– the use of the new operator.
• Here, the size is automatically decided based on the
number of values that are initialized.
Common data structures
Looping through an array
• An entire array is accessed using either simple for
statement or for-each statement.
• For example the program below is displaying a sum of all
the elements in a list.
Common data structures
Creating multi dimensional array
• An array with multiple dimensions can be created
by:
– Creating a 2-dimensional,
– 3-dimensional,
– any dimensional array.
• Multidimensional arrays are arrays of arrays.
• To create a multidimensional array variable, specify
each additional index using another set of square
brackets.
• The following syntax can be used to create two-
dimensional array.
Common data structures
Creating multi dimensional array
• When creating a two-dimensional array,
– it is created with a separate index for rows and columns.
• The individual element is accessed using the
respective row index followed by the column index.
• A multidimensional array can be initialized while it
has created using the following syntax:
Common data structures
Creating multi dimensional array
• When an array is initialized at the time of
declaration, it does not require to specify the size of
the array and use of the new operator.
• Here, the size is automatically decided based on the
number of values that are initialized.
Common data structures
1) Linear Data Structures
i. Arrays
Advantages
• Provide constant-time access to elements
– using an index.
• Simple and easy to understand.
• Memory is contiguous,
– leading to efficient memory access patterns.
Common data structures
1) Linear Data Structures
i. Arrays
Disadvantages
• Fixed size, making resizing inefficient and costly.
• Inefficient for insertions and deletions in the middle of
the array.
• Wasted space if the array size is larger than needed
Common data structures
1) Linear Data Structures
ii. linked Lists
• A linked list is another linear data structure,
– the elements are not stored at contiguous memory
locations.
• The elements in a linked list are linked using pointers.
• It consists of nodes, where each node contains a
value and a pointer to the next node.
Common data structures
1) Linear Data Structures
ii. linked Lists
Common data structures
1) Linear Data Structures
ii. linked Lists
Types of Linked Lists
• Singly Linked List: Each node points to the next.
• Doubly Linked List: Each node has pointers to both
the next and previous nodes.
Common data structures
1) Linear Data Structures
Types of Linked Lists
• Circular Linked List: The last node points back to
the first.
• Doubly Circular linked list: Contains a pointer to the
next as well as the previous node in the sequence.
Common data structures
1) Linear Data Structures
ii. linked Lists
Basic operations of Linked List
• InsertAtHead/addFirst: Adds an item to the beginning of
the list
• InsertAtEnd/addLast: Add an item to the end of the list.
• DeleteAtHead/RemoveFirst: Remove an item from the
beginning of the list.
• DeleteAtEnd/RemoveLast: Remove an item from the
end of the list.
• getFirst: Get the item at the beginning of the list.
• getLast: Get the item at the end of the list
Common data structures
1) Linear Data Structures
ii. linked Lists
Advantages
• Dynamic size, allowing for efficient insertions and
deletions anywhere in the list.
• No wasted space, as memory is allocated
dynamically.
• Simple implementation.
Common data structures
1) Linear Data Structures
ii. linked Lists
Disadvantages
• Inefficient for random access,
– requiring sequential traversal from the head to reach a
specific element.
• Additional memory overhead
– due to storing pointers/references for each node.
• More complex memory management compared to
arrays.
Common data structures
1) Linear Data Structures
iii. Stacks: A stack is a Last-In-First-Out (LIFO) data
structure.
• LIFO implies that the element that is inserted last,
comes out first.
• A real-life example of Stack could be a pile of books
placed in a vertical order
• In order to get the book that is somewhere in the
middle,
– all the books placed on top of it need to be removed
Common data structures
1) Linear Data Structures
iii. Stacks
Basic operations of stack
• Push: Add an item to the top
• Pop: Remove the top item
• isEmpty: Returns true if the
stack is empty
• Top/peek: Retrieves the top
item without removing it
Common data structures
1) Linear Data Structures
iii. Stacks
Advantages
• Simple and efficient for managing function calls,
recursive algorithms, and undo functionality.
• Provides Last In, First Out (LIFO) access pattern.
• Space-efficient, as memory is allocated only when
new elements are added.
Common data structures
1) Linear Data Structures
iii. Stacks
Disadvantages
• Limited access (only the top element is accessible).
• Limited functionality compared to more versatile data
structures like arrays and linked lists.
• Not ideal for searching or random access.
• May lead to stack overflow errors if the stack size
exceeds memory limits.
Common data structures
1) Linear Data Structures
iii. Stacks
Usage of stacks in computing
• They are how function calls get handled in a real
computer.
• To let people ‘undo’ things that they have done.
• To let people navigate backwards through a series of
operations.
Common data structures
1) Linear Data Structures
iv. Queues: A queue is a First-In-First-Out (FIFO)
data structure.
• example of Queue is a line of people waiting at an
ATM.
• If a new person comes,
– they will join the line from the end, not from the start.
• The person standing at the front will be the first to use
the ATM and hence leaves the line.
Common data structures
1) Linear Data Structures
iv. Queues
Basic operations of Queue
• Enqueue: Inserts an item at
the rear/end.
• Dequeue: Removes an
item from the front.
• isEmpty: Returns true if the
queue is empty.
• Top/peek: Retrieve the
front item.
Common data structures
1) Linear Data Structures
iv. Queues
Advantages
• Provides First In, First Out (FIFO) access pattern,
– suitable for task scheduling and process management.
• Efficient for managing waiting lines and message
queues.
• Supports operations like enqueue and dequeue with
constant time complexity.
Common data structures
1) Linear Data Structures
iv. Queues
Disadvantages
• Limited access (only front/rear accessible).
• Slower than arrays for indexed access.
• Limited functionality compared to more complex
data structures like trees and graphs.
THE END