Data structure
Array - is a data structure consisting of a group of elements that are accessed by indexing. In most programming languages each element has the same data type and the array occupies a contiguous area of storage.
pseudo-code
- a mixture of a natural language and high level programming concept that described the main ideas behind a genetic implementation of a data structure or algorithm
- it is more structured than usual prose but less formal than a programming language.
stacks- a last in first out (LFO) dta structure" Inside the stacks"
Push- inserting or placing an item inside the stack.
Pop- removes an item from the stacks
- remove the top element of the stacks.
Top- examines the top element of the stacks.
Empty- return true if and only if the stacks contains nothing. Null (value is 0).
Evaluation of expressions
-MDAS RULE
- if the outside is greater push (outside)
-if outside is lower/or equal -Pop(top)
- Push(Outside)
1. Infix Notation
- operand operator operand
2. Post Fix Notation
- operand operand operator
3. Prefix Notation
- operator operand operand
Queues- is a sequential organization of data.
4 basic operation for a queue
En queue- insert an item at the end of the queue.
Head(Front)- examine the front/head item of the queue.
De queue- remove the front item from the queue.
Empty- return true if and only if the queue contains nothing.
2 Kinds of Queue.
Simple and Priority- organized items in a line where the first item is at the back of the line.
Priority queue- is similar to a simple queue in the items are organized in a line and processed sequentially.
Link List-is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order. A linked list is a self-referential data type because it contains a pointer or link to another datum of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access.
Types of linked List
Linearly linked list
Singly-linked list
The simplest kind of linked list is a singly-linked list (or slist for short), which contains a node having two fields, one is information field and another is link field. This link points to the next node in the list, and last node points to a null value
A singly-linked list containing two values: the value of the current node and a link to the next node
A singly linked list's node is divided into two parts. The first part holds or points to information about the node, and second part holds the address of next node. A singly linked list travels one way.
Doubly-linked list
A more sophisticated kind of linked list is a doubly-linked list or two-way linked list. Each node has two links: one points to the previous node, or points to a null value or empty list if it is the first node; and one points to the next, or points to a null value or empty list if it is the final node.
A doubly-linked list containing three integer values: the value, the link forward to the next node, and the link backward to the previous node
In some very low level languages, XOR-linking offers a way to implement doubly-linked lists using a single word for both links, although the use of this technique is usually discouraged.
Circularly-linked list
In a circularly-linked list, the first and final nodes are linked together. This can be done for both singly and doubly linked lists. To traverse a circular linked list, you begin at any node and follow the list in either direction until you return to the original node. Viewed another way, circularly-linked lists can be seen as having no beginning or end. This type of list is most useful for managing buffers for data ingest, and in cases where you have one object in a list and wish to iterate through all other objects in the list in no particular order.
The pointer pointing to the whole list may be called the access pointer.
Binary Tree- is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. Binary trees are commonly used to implement binary search trees and binary heaps.
2 rules about parents
1. The roots has no parents
2. Every other node has exactly one parent.
Sibling- 2 nodes with the same parent
Internal node- node with at least 1 child.
External node- node without children.
Ancestor-parent , grandparent, grand- grandparent.
Depth- number of ancestor.
Descendant- Child granchild, grand- grandchild.
Binary Tree Traversal
Traversal- is the process of visitng every node once.
Technique:
Pre order- the root is visited before the sub tree traversal.
Rules: Root, Left Right
In order- the root is visited in between left and right sub tree traversal.
Rules: Left, Root, Right
Post order- the root visited after the sub tree traversal.
Rules:Left, right root
Sorting -is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:
- The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
- The output is a permutation, or reordering, of the input.
Bubble sort-is a straightforward and simplistic method of sorting data that is used in computer science education. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, it swaps them.
Insertion sort - is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list
Shell Sort- It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort.
Merge sort- takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n).
Heapsort- is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree.
Quicksort -is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.
