Practical Session #4 - ADTs: Array, Queue, Stack, Linked List Basic Data Structures and Abstract Data Types Abstract Data Type ADT A collection of data-storing entities with operations to create, access, change, etc. A linear sequence of elements that supports access to its elements by their indexes. Supports the following basic methods: elementAt(i) returns the element at index i – Array insertAt(i, element) insert new element at index i – removeAt(i) remove the element in index i – size() returns the size of the array – FIFO - First In First Out ADT that supports the following operations: Queue Enqueue - insert new element at the tail of the queue Dequeue - remove element from the head of the queue isEmpty - returns true if the queue is empty LIFO - Last In First Out ADT that supports the following operations: Stack Push - add element to the head of the stack Pop - remove element from the head of the stack isEmpty - returns true if the stack is empty A data structure with linear access to the elements in it. Linked List Each element has a pointer to the next element in the list A data structure with linear access to the elements in it. Each element has 2 pointers, one to the next element in the list and the List other to the previous element Important! in a variety of possibilities. Below we – ADT’s can be implemented describe and demonstrate their implementations. ADT’s Question 1
Practical Session #4 - ADTs: Array, Queue, Stack, Linked List Basic Data Structures and Abstract Data Types ADT Abstract Data Type A collection of data-storing entities with operations to create, access, change, etc. Array A linear sequence of elements that supports access to its elements by their indexes. Supports the following basic methods: elementAt(i) – returns the element at index i insertAt(i, element) – insert new element at index i removeAt(i) – remove the element in index i size() – returns the size of the array Queue FIFO - First In First Out ADT that supports the following operations: Enqueue - insert new element at the tail of the queue Dequeue - remove element from the head of the queue isEmpty - returns true if the queue is empty Stack LIFO - Last In First Out ADT that supports the following operations: Push - add element to the head of the stack Pop - remove element from the head of the stack isEmpty - returns true if the stack is empty Linked List A data structure with linear access to the elements in it. Each element has a pointer to the next element in the list List A data structure with linear access to the elements in it. Each element has 2 pointers, one to the next element in the list and the other to the previous element Important! – ADT’s can be implemented in a variety of possibilities. Below we describe ADT’s and demonstrate their implementations. Question 1
ps4.docx