4.1Data Structures and their Applications Flashcards
Why Study Data Structures?
❑Data structures are the “foundation stone” of all algorithms
❑Do not build on bad foundations…
❑Representing the problem you are solving correctly will vastly help in designing a solution
❑The use of the correct data structure will speed up an algorithm
❑E.g. Sorting a list of 1,000 names
b❑You would use a String array rather than 1,000 String variables!❑We can measure how good is a particular data structure by using Big-Oh notation
Lists
❑A listis a sequence of zero or more data items
❑The total number of items is said to be the lengthof the list
❑The length of a given list can grow and shrink on demand
❑Items can be accessed, inserted, or deleted at any position in a list
Array Implementation
❑Arrays are the simplest and most widely used data structures ❑Maintain insertion order of elements
❑An Arrayis a structure of fixed-size that can hold a collection of similar items
❑ArrayListis a variable length Collection class. They can increase or decrease the size dynamically
LinkedList Implementation
❑Implementation of the List interface
❑Maintain the insertion order of elements
❑Elements are not indexed –when searching, start with the head and work our way through…
Stacks
❑A stack is a special kind of list in which all insertions and deletions take place at one end
❑This is called the top
❑It has another name: “pushdown list‘”
❑Its items are added and deleted on a last-in-first-out (LIFO) basis
Using Stacks
❑To add an item to a stack, you push an item onto the top
❑To remove an item from the top you popit
❑In the example below the top of the stack is on the right hand sid
Queues
❑A queue is another special kind of lis
❑Items inserted at one end (the rear)
❑Items deleted at the other end (the front)
❑A queue is a FIFOtype data structure
❑The items are deleted in the same order as they were added
❑On a first-in-first-out basis
❑For a queue structure, we have two special names for insertion and deletion:
❑ENQUEUE (insertion)
❑DEQUEUE (deletion
Hash Tables
❑A Hash table or Hash Map is a data structure that maps a key to a Value
❑A special function called a Hash Function performs this mapping
❑This function usually maps the key to an index in an array
❑Key and value could be any type of data structure
Directed Graph
❑A directed graph is a pair G=(V, E)
❑Where V is the set of vertices, and E is a set of ordered pairs of elements of V
❑For directed edges (v, w)in E, vis tail, wis head
n
❑It can be represented as v→wor vw
Undirected Graph
❑An undirected graph is a pair G=(V, E), where E is a set of unordered pairs of distinct elements of V
❑Edges have no orientation
❑For undirected graphs, vw = wv
Complete Graph
❑A complete graph is normally an undirected graph with an edge between each pair of vertices
Paths
A sequence of k vertices, [v1, v2, …, vk], such that any pair of consecutive vertices, vi, vi+1are adjacent (connected by an edge) is called a path
Connectivity
❑An undirected graph is connected if and only if for each pair of vertices v and w, there is a path from v to w
❑A directed graph is strongly connected if and only if for each pair of vertices v and w, there is a path from v to w
Weighted Graph
The weights in a weighted graph are usually represented as numbers centred near to the edges they apply to
How do we represent a graph when it comes to implementation?
❑We often represent a graph as a matrix (2D array), although other data structures can be used depending on the application
❑If we have N nodes to represent
❑For an Nby Nmatrix G, a non-zero value of gij(ithrow, jthcolumn of G) means there is an edge between node iand j
❑Undirected
❑We assume that gijis the same as gji
❑Directed
❑gijis not always the same as gji
❑Non-weighted
❑gijis either one for an edge or zero for no edge
❑Weighted
❑gijis the edge weight or zero for no edge
❑Complete
❑gijis never zero
