[go: up one dir, main page]
Scribd
Upload
34 views26 pages

OOP - Lecture 7

The document discusses different types of data structures including linear data structures like arrays, linked lists, queues, and stacks as well as non-linear data structures like trees and graphs. It explains the basic concepts, properties, and common operations for each type of data structure.

Uploaded by

ghazal.hpr5
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
34 views26 pages

OOP - Lecture 7

The document discusses different types of data structures including linear data structures like arrays, linked lists, queues, and stacks as well as non-linear data structures like trees and graphs. It explains the basic concepts, properties, and common operations for each type of data structure.

Uploaded by

ghazal.hpr5
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/ 26

What is a Data Structure

• It is a format for arranging, processing, accessing and storing a


collection of data in a storage device.
• There are both simple and complex data structures.
• Using a proper data structure for your data can increase the
performance of your program by
• Efficiency
• Reusability
• Processing speed
• Linear Data Structures
• Elements arranged in a linear fashion
• Each element is connected to one other element only

• Non-Linear Data Structures


• Elements arranged in a non-linear fashion
• Each element is connected to n-other elements
Static vs dynamic
• Static Data Structures
• Size is declared and fixed at compile time
• Can not store data over the fixed size
• Easy to handle
• Can occupy more storage then required

• Dynamic Data Structures


• Size is not fixed at compile time
• Size can be decided on runtime
• Does occupy storage as required
• Releases memory when no longer needed
Array
• Advantages
• Random access
• Easy sorting and iteration
• Replacement of multiple variables
• Disadvantages
• Size is fixed
• Difficult to insert and delete
• If capacity is more and occupancy less, most of the array gets wasted
• Needs contiguous memory to get allocated
Dynamic Array: ArrayList
Linked Lists
• Linked list
• Linear collection of self-referential classes (nodes)
• Connected by reference links
• Nodes can be inserted and deleted anywhere in linked list
• Last node is set to null to mark end of list
Linked Lists (cont.)
firstNode lastNode

H D ... Q

A graphical representation of a linked list.


Linked Lists (cont.)
(a ) firstNode
7 11

new ListNode
12

(b ) firstNode
7 11

new ListNode
12

The insertAtFront operation.


Linked Lists (cont.)
(a ) firstNode lastNode new ListNode

12 7 11 5

(b ) firstNode lastNode new ListNode

12 7 11 5

A graphical representation of the insertAtBack operation.


Linked Lists (cont.)
(a ) firstNode lastNode

12 7 11 5

(b ) firstNode lastNode

12 7 11 5

removeItem

A graphical representation of the removeFromFront operation.


Linked Lists (cont.)
(a ) firstNode lastNode

12 7 11 5

(b ) firstNode current lastNode

12 7 11 5

removeItem

A graphical representation of the removeFromBack operation.


import java.util.LinkedList;
import java.util.ListIterator;

public class ListDemo {


public static void main(String[] args) {
LinkedList<String> staff = new LinkedList<>();
staff.addLast("Diana");
staff.addLast("Harry");
staff.addLast("Romeo");
staff.addLast("Tom");

// | in the comments indicates the iterator position

ListIterator<String> iterator = staff.listIterator(); // |DHRT


iterator.next(); // D|HRT
iterator.next(); // DH|RT

// Add more elements after second element

iterator.add("Juliet"); // DHJ|RT
iterator.add("Nina"); // DHJN|RT

iterator.next(); // DHJNR|T

// Remove last traversed element

iterator.remove(); // DHJN|T

// Print all elements

System.out.println(staff);
System.out.println("Expected: [Diana, Harry, Juliet, Nina, Tom]");
}
}
ArrayList vs LinkedList
ArrayList LinkedList
ArrayList uses the dynamic array structure LinkedList uses the linkedList (doubly) structure
Data manipulation is slower Data manipulation is faster
Data access is faster Data access is slower
Classic Data Structures
• Now we'll examine some common data structures that
are helpful in many situations
• Classic linear data structures include queues and stacks
• Classic nonlinear data structures include trees and
graphs
Queues
• A queue is a list that adds items only to the rear of the
list and removes them only from the front
• It is a FIFO data structure: First-In, First-Out
• Analogy: a line of people at a bank teller’s window
Queues
• Classic operations for a queue
• enqueue - add an item to the rear of the queue
• dequeue (or serve) - remove an item from the front of the
queue
• empty - returns true if the queue is empty

• Queues often are helpful in simulations or any situation


in which items get “backed up” while awaiting processing
Stacks
• A stack ADT is also linear, like a list or a queue
• Items are added and removed from only one end of a
stack
• It is therefore LIFO: Last-In, First-Out
• Analogies: a stack of plates or a stack of books
Stacks
• Stacks often are drawn vertically:
Stacks
• Clasic stack operations:
• push - add an item to the top of the stack
• pop - remove an item from the top of the stack
• peek (or top) - retrieves the top item without removing it
• empty - returns true if the stack is empty

• A stack can be represented by a singly-linked list, with the first


node in the list being to top element on the stack
• A stack can also be represented by an array, with the bottom of the
stack at index 0
Trees
• A tree is a non-linear data structure that consists of a
root node and potentially many levels of additional nodes
that form a hierarchy
• Nodes that have no children are called leaf nodes
• Nodes except for the root and leaf nodes are called
internal nodes
• In a general tree, each node can have many child nodes
A General Tree
Binary Trees
• In a binary tree, each node can have no more than two
child nodes
• Trees are typically are represented using references as
dynamic links
• For binary trees, this requires storing only two links per
node to the left and right child
Graphs
• A graph is another non-linear structure
• Unlike a tree, a graph does not have a root
• Any node in a graph can be connected to any other node
by an edge
• Analogy: the highway system connecting cities on a map
Graphs

You might also like