INTRODUCTION
An abstract data type is a data structure abstraction that only provides the interface that the data structure must abide by. The interface provides no specifics about how something ought to be implemented or in which programming language.
LIST
A List is an abstract data type that is executed with the help of a dynamic array and a linked list. A queue can be built using a linked list-based queue, an array-based queue, or a stack-based queue. A tree map, hash map, or hash table is used to implement a map.
ADTs are a popular and important type of data. ADTs are mathematical or logical ideas that can be executed on various machines using various languages. Moreover, they are very adaptable and do not rely on languages or machinery.
A list is an ordered set of information of the same type. A list also has a limited number of values. Different data types cannot be stored in the same list.
Using an array, we can easily execute a list. Memory management, on the other hand, is a significant task for the implementation of a list using an array. An array must have a fixed size in every programming language. Furthermore, there is no meaningful maximum size that we can specify for an array. As a result, when using an array, a list will occasionally overflow.
TYPES OF LIST
An ordered list is one that is arranged alphabetically or numerically.
In an unordered list, the elements are not arranged in any order based on their characteristics. As a result, we'll arrange the elements in the order that is most convenient for the user.
Elements are arranged in an indexed list, but their numerical positions are referred to as indexes. As a result, we can use indexes to access features in a list.
OPERATIONS ON THE LIST
TIME COMPLEXITY
The time complexity of obtaining any element is O (1). Furthermore, the insertion and deletion from the end of a list are not influenced by the list's size. As a result, the insertion and deletion from end take the same amount of time.
Inserting or removing an element at the top of the list can take some time. In this case, we must shift all of the elements in proportion to the length of the list. As a result, the time complexity would be O (N).
QUEUE
A queue is a linear ADT with limitation that insertion can only occur at one end and deletion can only occur at the other. It operates on the FIFO principle (first-in, first-out).
TYPES OF QUEUES
- A simple queue is the most basic type of queue ADT. It plugs data from the back end while removing elements from the front. Furthermore, a simple queue strictly follows FIFO.
- A circular queue has a circular structure because the first element in the queue points to the last element in the queue. It makes better use of memory than a simple queue.
- The priority queue is a special queue that stores a primacy for each element in the queue. A priority queue handles insertion and removal operations based on the importance assigned to each element.
The FIFO rule is not followed by a double-ended queue. We have the ability to insert and eliminate elements from both the front and rear ends.
OPERATIONS ON THE QUEUE
IMPLEMENTATION OF QUEUE
The main issue with using an array to implement a queue is that it will only work when the queue size is known. Furthermore, the queue size should be fixed.
The address of the last inserted element is stored in the rear. The front, on the other hand, stores the address of the initial inserted element
Insertion and deletion have a time complexity of O(1). However, in the worst case, searching for an element in a particular queue takes O(N) time.
STACKS
TYPES OF STACKS
1 > It contains fewer data.
2> The stack depth in a memory register is adjustable.
OPERATIONS
IMPLEMENTATION OF STACK
A linked list can be used to implement a stack. We can expand the size of the stack at runtime because memory can be allocated dynamically.
The variable Top has a pointer that stores the location of the most newly acquired node. To remove an element from the stack, we relocate the element highlighted by the Top variable by pointing to the linked list's previous node. When the stack is initially empty, the Top points to null
The time complexity of inserting and removing an element from the stack is O(1). However, removing the last element from the stack would have a time complexity of O(N).