An abstract data type (ADT) is a data type which defines operations for the type without specifying the implementaiton details.
A list is an ADT describing operations for ordered data, such as append, remove, search or print the list.
A singly-linked list is a data structure implementing a list ADT. A linked list has nodes, where each node has data and a pointer to the next node.
The first node is called a head. The last node is called the tail.tailA singly-linked list's first node is called the head, and the last node the tail.
In a singly-linked list each element contains a point to the next and/or previous element in the list.
In a doubly-linked list each node has data, a pointer to the next node, and a pointer to the previous node.
A stack is a last in, first out (LIFO) ADT in which items can only be inserted on or removed from the top of a stack. e.g. A stack of plates in the cafeteria. Common operations on a stack are push: insert item on the top and pop, remove and return item on the top.
A queue is a first in, first out (FIFO) ADT in which items are inserted at the end and removed from the front of the queue. e.g. A line in the cafeteria. Common queue operations are enqueue: insert an item at the end of the queue, and dequeue: remove and return the item at the front of the queue.
- Imgs credit: Wikipedia
zyBooks Ch 7.1 - 7.6, 7.9, 7.10, 7.13, 7.15
https://github.com/ava11235/it212/blob/main/ListNode.java
https://github.com/ava11235/it212/blob/main/LinkedIntList.java
https://github.com/ava11235/it212/blob/main/ListTest.java
zyBooks Ch 7.1 - 7.6, 7.9, 7.10, 7.13, 7.15 Participation Activities
Upon successful completion of the material, students will be able to:
- Define the Linked List ADT and apply its operations to solving coding problems.
- Define the Stack ADT and apply its operations to solving coding problems.
- Define the Queue ADT and apply its operations to solving coding problems.
- Implement a singly-linked class of integers.