This third meeting the material will be hosted by pa sky . The main topic of today meeting is linked list 2 .
Linked List
Linked list is a linear collection of data elements, called nodes pointing to the next node by means of pointer. It is a data structure consisting of a group of nodes which together represent a sequence.
There are two modifiers that can modifies the node there are push(its use for adding a node value and push to create the node ) and pop(delete a node ) .
Linked List is divided by 2 kinds there are single linked list and double linked list .
Single linked list
Single Linked Lists are a type of data structure. It is a type of list. In a single linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node. It is called a single linked list because each node only has a single link to another node. To store a single linked list, you only need to store a reference or pointer to the first node in that list. The last node has a pointer to nothingness to indicate that it is the last node.
Double Linked List
double linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
1.Queue
Queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. Linked list is a data structure consisting of a group of nodes which together represent a sequence. Here we need to apply the application of linked list to perform basic operations of queue.
There are two kind of queue that can be used for programming there are circular queue and priority queue
Circular queue
- Single Circular queue linked list:
It is an extension for the basic single linked list. In circular linked list Instead of storing a Null value in the last node of a single linked list, store the address of the 1st node (root) forms a circular linked list. Using circular linked list it is possible to directly traverse to the first node after reaching the last node.
This shows a single circular queue on liked list
- Using circular queue on double linked list
In double linked list the right side pointer points to the next node address or the address of first node and left side pointer points to the previous node address or the address of last node of a list. Hence the above list is known as circular double linked list.
This shows a single circular queue on double liked list
Priority queue
- priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority.
2.Stack
Stack is a type of queue that in practice is implemented as an area of memory that holds all local variables and parameters used by any function, and remembers the order in which functions are called so that function returns occur correctly. Each time a function is called, its local variables and parameters are “pushed onto” the stack. When the function returns,these locals and parameters are “popped.” Because of this, the size of a program’s stack fluctuates constantly as the program is running, but it has some maximum size. stack is as a last in, first out (LIFO) abstract data type and linear data structure. Linked list is a data structure consisting of a group of nodes which together represent a sequence. Here we need to apply the application of linkedlist to perform basic operations of stack.
IF you want to now the details about how stack implementation really works here i found a really cool website that can let you experiment on stack liked list :
click here –>Stack (Linked List Implementaion)
3.Evaluation on prefix notation
To operate this evaluation there are three tings that you have to know :
- Inflix : the normal operation that we normally use to calculate our math problems .
- Prefix : a calculation of math problems that operator have to be on the left followed by right operand and left operand . usually its use for programming purpose because computer can detect math problems more easier in prefix .
- postfix : is the opposite of prefix that the operator have to be on the right followed before operand right and perand left .
EXP:
inflix : 4+6*(5-20)/3
Prefix : +4/*6-5 3
Postfix: 4652-*3/+
4. DFS and BFS
- Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
- Bread-first search(BFS)This can be through of as being like Dijkstra’s algorithm for shortest paths, but with every edge having the same length. However it is a lot simpler and doesn’t need any data structures. We just keep a tree (the breadth first search tree), a list of nodes to be added to the tree, and markings (Boolean variables) on the vertices to tell whether they are in the tree or list.
IF you want to now the details about how BFS and DFS implementation really works here i found a really cool website that can let you experiment on method of seach:
click here –>BFS Implementation
click here –>DFS Implementation