[SOLVED] CS Abstract Data Types: Lists 1

Abstract Data Types: Lists 1
The List ADT
A List interface and its implementation: Array List
Structured Programming 1110/1140/6710

Copyright By Assignmentchef assignmentchef

Abstract Data Types: Lists A1
Abstract Data Types (ADTs)
Abstract data types describe the behaviour (semantics) of a data type without specifying its implementation. An ADT is thus abstract, not concrete.
A container is a very general ADT, serving as a holder of objects. A list is an example of a specific container ADT.
An ADT is described in terms of the semantics of the operations that may be performed over it.
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
The List ADT
The list ADT is a container known mathematically as a finite sequence of elements. A list has these fundamental properties:
duplicatesareallowed order is preserved
A list may support operations such as these:
create: construct an empty list
add: add an element to the list
is empty: test whether the list is empty
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
Our List Interface
We will explore lists using a simple interface:
public interface List { void add(T value);
T get(int index);
int size();
T remove(int index);
void reverse(); }
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
void add(T value); T get(int index); int size();
T remove(int index); void reverse(); String toString();
ABCD4 A B CD C DA B DCA
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A1
List Implementation
Fast lookup of any element
A little messy to grow and contract
Linkedlist
Logical fit to a list, easy to grow, contract
Need to traverse list to find arbitrary element
Structured Programming 1110/1140/6710

Abstract Data Types: Lists 2
A List interface and its implementation: Linked List
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A2
List Implementation: Linked Lists
Fast lookup of any element
A little messy to grow and contract
Linkedlist
Logical fit to a list, easy to grow, contract
Need to traverse list to find arbitrary element
public class LinkedList { private class LLNode {
LLNode next;
LLNode start;
LLNode end;
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A2
Linked List Reversal
CBA start end
Structured Programming 1110/1140/6710

Abstract Data Types: Lists A2
Linked List Reversal
Pointer reversal
reverse end
ABCD start
Structured Programming 1110/1140/6710

Abstract Data Types: Sets
The Set ADT A Set Interface
Structured Programming 1110/1140/6710

Abstract Data Types: Sets A3
The Set ADT
The set ADT corresponds to a mathematical set. A set has these fundamental properties:
duplicatesarenotallowed order is not preserved
A set may support operations such as these:
create:constructanemptyset
add:addanelementtotheset
contains:doesthesetcontainagivenelement remove: remove an element from the set
Structured Programming 1110/1140/6710 23

Abstract Data Types: Sets A3
Our Set Interface
We will explore sets using a simple interface :
public interface Set { boolean add(T value); boolean contains(T value); int size();
boolean remove(T value); }
Structured Programming 1110/1140/6710 24

Abstract Data Types: Hash Tables
Hash Table Implementation of a Set 1
Structured Programming 1110/1140/6710

Abstract Data Types: Hash Table A4
Hash Tables
A hash table stores (key, value) pairs, using a hash function to map a key into a table. Key challenges are: a) dealing with hash collisions, and b) dealing with load (how big to make the table).
Two broad approaches: Separate chaining
Hash table entries are lists. (key, values) are in lists.
Openaddressing
Hash table entries are (key, value) pairs.
Collisions resolved by probing e.g. find next empty slot
Structured Programming 1110/1140/6710 28

Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710

Abstract Data Types: Hash Table A4
fruit.add(apobaoparerppnaralnariegcnoae)e)t)))
Structured Programming 1110/1140/6710

fruit.contains(fmoiraanggno)ge))
Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710

Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710 32

Abstract Data Types: Hash Table A4
Structured Programming 1110/1140/6710 33

Abstract Data Types: Hash Table A4
fruit.contains(gfoiraganpge)e))
Structured Programming 1110/1140/6710 34

Abstract Data Types: Trees
The Tree ADT Implementation of a Set 2
Introduction to Software Systems 1110/1140/6710

Abstract Data Types: Trees A5
The Tree ADT
The tree ADT corresponds to a mathematical tree. A tree is defined recursively in terms of nodes:
Atreeisanode
Anodecontainsavalueandalistoftrees. Nonodeisduplicated.
Introduction to Software Systems 1110/1140/6710 14

Abstract Data Types: Trees A5
Binary Search Tree
A binary search tree is a tree with the following additional properties: Eachnodehasatmosttwosub-trees
Nodesmaycontain(key,value)pairs(orjustkeys)
Keysareorderedwithinthetree:
The left sub-tree only contains keys less than the nodes key
The right sub-tree only contains keys greater than the nodes key
Introduction to Software Systems 1110/1140/6710 15

Abstract Data Types: Trees A5
peach fruit
Introduction to Software Systems 1110/1140/6710 16

Abstract Data Types: Trees A5
Introduction to Software Systems 1110/1140/6710 17

Abstract Data Types: Trees A5
fruit.contains(fgoirgapn)ege))
Introduction to Software Systems 1110/1140/6710 18

Abstract Data Types: Maps
The Map ADT
A Map interface and its implementation ADT Recap
Structured Programming 1110/1140/6710

Abstract Data Types: Maps A6
First-principles implementation of three Java container types: List
ArrayList, LinkedList implementations (A1, A2) Set
HashSet, BSTSet implementations (A3, A4, A5) Map
HashMap, BSTMap implementations (A6) Introduced hash tables, trees (A4, A5)
Structured Programming 1110/1140/6710 12

Abstract Data Types: Maps A6
The Map ADT (A.K.A. Associative Array)
A map consists of (key, value) pairs
Each key may occur only once in the map
Values are retrieved from the map via the key Values may be modified
Key, value pairs may be removed
Structured Programming 1110/1140/6710 13

Abstract Data Types: Maps A6
Our Map Interface
We will explore maps using a simple interface:
public interface Map { V put(K key, V value);
V get(K key);
V remove (K key);
int size(); }
Structured Programming 1110/1140/6710 14

Abstract Data Types: Maps A6
fruit.pgpueut(oagrpraranipgceeot,,)73..0500))
Structured Programming 1110/1140/6710 15

Abstract Data Types: Maps A6
fruit.pgpueut(oagrpraranipgceeot,,)73..0500))
Structured Programming 1110/1140/6710 16

CS: assignmentchef QQ: 1823890830 Email: [email protected]