Lesson 3 Flashcards
_______ is a sequence of data structures, which are connected together via links. It is a sequence of links which contains items. Each link contains a connection to another link. This is the second most-used data structure after array.
Linked List
Each link of a linked list can store a data called an _______.
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
True or false:
Linked List contains a link element called first.
True
True or False:
Each link carries a data field(s) and a link field called next.
True
True or False:
Each link is linked with its next link using its next link.
True
True or False:
Last link carries a link as null to mark the end of the list.
True
______ can be visualized as a chain of nodes, where every node points to the next node
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
Basic Operations supported by a list:
Adds an element at the beginning of the list.
Insertion
Basic Operations supported by a list:
Deletes an element at the beginning of the list.
Deletion
Basic Operations supported by a list:
Displays the complete list.
Display
Basic Operations supported by a list:
Searches an element using the given key.
Search
Basic Operations supported by a list:
Deletes an element using the given key.
Delete
_________ is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.
Doubly Linked List
Each link of a linked list contains a link to the previous link called _____.
Prev
A ______ contains the connection link to the first link called First and to the last link called Last.
LinkedList
The way to write arithmetic expression is known as a ______. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression.
notation
The 3 notations are:
Infix Notation
Prefix (Polish) Notation
Postfix (Reverse-Polish) Notation
We write expression in _________, e.g. a - b + c, where operators are used in-between operands.
infix notation
In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +ab. This is equivalent to its infix notation a
+ b. Prefix notation is also known as ________.
Prefix/Polish Notation
This notation style is known as _________. In this notation style, the operator is postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is equivalent to its infix notation a + b.
Reversed Polish Notation/Post Notation
When an operand is in between two different operators, which operator will take the operand first, is decided by the ________ of an operator over others.
precedence
___________ describes the rule where operators with the same precedence appear in an expression. For example, in expression a + b − c, both + and – have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c.
Associativity
___________ is an abstract data structure, somewhat similar to Stacks. Unlike stacks, this is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). It follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.
Queue
Basic operations of Queue:
Enqueue()
Dequeue()
Add (store) an item to the queue
enqueue()
Remove (access) an item from the queue.
dequeue()
Gets the element at the front of the queue without removing it.
peek()
Checks if the queue is full.
isfull()
Checks if the queue is empty.
isempty()
True or False:
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer
True
