Module 3: Linked List and Queue Flashcards
It is a sequence of data structures, which are connected together via links
Linked List
True or false: Each link contains a connection to another link
True
What is the second most-used data structure after array?
Linked List
What stores data or elements in a linked list?
Link
Each link of a linked list contains a link to the next link called?
Next
A ____ contains the connection link to the first link called First
Linked List
What is being described:
1. Contains a link element called First
2. Carries data fields and a link field called next
3. Link is linked with its next link using its next link
4. Last link carries a link as null to mark the end of the list
Linked list
What are the different types of linked list?
Simple Linked List
Doubly Linked List
Circular Linked List
Item navigation is forward only
Simple Linked List
Items can be navigated forward and backward
Doubly Linked List
Last item contains link of the first element as next and the first element has a link to the last element as previous
Circular Linked List
What are the basic operations supported by a linked list?
Insertion, Deletion, Display, Search, Delete
Adds an element at the beginning of the list
Insertion
Deletes an element at the beginning of the list
Deletion
Displays the complete list
Display
Searches an element using the given key
Search
Deletes an element using the given key
Delete
Variation of a linked list where navigation is possible both ways
Doubly Linked List
Terms in doubly linked list:
Link, Next, Prev, LinkedList
True or False: Infix notations are first converted to postfix or prefix notations and then computed
True
This is the way to write arithmetic expressions
Notation
Notation where operators are used in-between operands
Infix Notation
Notation where operators are written ahead of operands
Prefix/Polish Notation
Notation where the operator is written after the operands
Postfix/Reversed Polish Notation
What to consider in converting infix notation to prefix or postfix notation?
Precedence of operators (PEMDAS),
Associativity (Left Associative)
Abstract data structure similar to stacks, but it is open at both ends
Queue
Add (store) an item to the queue
Enqueue
Remove (access) an item from the queue
Dequeue
True or False: Queue can be implemented using arrays, linked lists, pointers, and structures
True
Operations in queue:
peek()
isfull()
isempty()
Checks if the queue is full
isfull()
Gets the element at the front of the queue without removing it
peek()
Checks if the queue is empty
isempty()
What pointer is used to dequeue or access data?
Front pointer
What pointer is used to enqueue or store data
Rear pointer
Steps in enqueuing:
- Check if full
- If full -> return 0;
- If not full, increment rear pointer to the next empty space
- Add data element
- Return success
Steps in dequeuing:
- Check if empty
- If empty, return 0;
- If not empty, access data pointed by front pointer
- Increment front pointer to the next available data element
- Return success
