Skip to main content

HALF SEMESTER SUMMARY

Data Structures Summary

Dear reader, due to the recent outbreak of the COVID-19 pandemic, we've all been forced to study at home. It is a challenge to keep track of the subject matter, so in this blog, I will be putting all my summary about what I've learned in this half semester from Data Structures. I've been thinking about the final project of making a pacman game using linked list... I can make a pacman game with 2d arrays, but a Linked List as a map ? It still leaves me in confusion ... For now I'll be studying more too be closer on approaching the final project




Linked List II, a linear data structure where each element is a separate object.

Materials :
- Circular Linked List
- Circular Single Linked List
- Doubly Linked List
- Circular Doubly Linked List



Circular Linked List

Circular Single Linked List is a variation of linked list which its first element
points to the last element and the last element points to the first element.
In this list, there is no NULL values stored.





Circular Single Linked List

In a circular Singly linked list, the last node of the list refers to the first node of the list.






Doubly Linked List

Doubly Linked List is a linked list of data which have two links each node, one that refer to the previous data and one that refer to the next data.

Code Example :

struct Node {
    int data;
    struct Node* next; 
    struct Node* prev; 
};

Circular Doubly Linked List

Circular Doubly Linked List are linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node refers to first node by next pointer and also the first node refers to last node by previous pointer.




Linked List, is a concept which is I'd say pretty understandable, but when it comes to coding it, we all know, coding something for the first time would be a challenge. Luckily, at Binus Data Structures big  class, they decided to teach some code logic, and this is what i've learned from it.
  • Struct
struct Data
{
    int value;
    struct Data *next,*prev;
}*head,*curr,*tail;

  • Push tail (insert sebuah data di paling belakang)
void push(int a)
{
    curr = (struct Data*)malloc(sizeof(struct Data));
    curr->value = a;

    if(head==NULL){
        head = tail = curr;
    }
    else{
        tail->next = curr;
        curr->prev = tail;
        tail = curr;
    }
    head->prev = tail->next = NULL;
}
  • Print isi dalam linked list
void cetak()
{
    curr = head;
    while(curr!=NULL){
        printf("%d\n",curr->value);
        curr = curr->next;
    }
}
  • PopTail(Delete data paling belakang)
void pop()
{
    curr = head;
    
    if(tail == head){
        free(curr);
        tail = head = curr = NULL;
    }
    else
    {
        while(curr->next!=tail){
            curr = curr->next;
        }
        free(tail);
        tail = curr;
        tail->next = NULL;
    }
}

Those are the codes i learned from Big Class of Data Structures 

GSLC KE-2 Data Structure, Pertemuan ke-6
Materi :
- Hashing and Hash Tables
- Tree and Binary Tree

Hashing and Hash Tables

Hashing is a method used to store data so it can be added, search and delete in a short time.
There are many ways of hashing.
 Hash Functions :

  • Mid-square : Squaring the value of key, taking the middle part.

  • Division : (key) mod (value).

  • Folding : Done by taking parts of a number, adding it, and ignoring some digits of it.

  • Digit Extraction : Extract some digit from a number. for example, given x=219382. We want to extract some of it's digit and make it a hash key, so we extract 1st digit and 4th digit. From that the number we get is 23. 
  • Rotating Hash : Do any of the method above, then rotate the digit. For example, given that x=23354. If we rotate x, it would be 45332.
In some case, Collision will happen... What is a collision ? Collision is when several data have the same hash-key. What can we do to handle it ?
  • Linear Probing : Search the next empty slot and put the data there.
  • Chaining : Put the string n a slot as a chained list (Linked List).
Trees & Binary Tree

Tree ? What is it ? A tree is a non-linear data structure that represents the relationships ammong data objects.
Root = Node at the top (A)
Leaf = Nodes that do not have Children(E,F,G)
Degree = Total sub tree of a node
Height/Depth = maximum degree of nodes in a tree

Meanwhile, Binary Tree is a rooted tree data structure which each node has at most(max) two children.
Type of Binary Tree
- Perfect binary tree, which every level of the binary tree are at the same depth
- Complete binary tree, a binary tree in which every level except the last(optional), is completely filled. If a binary tree is perfect, it is also a complete binary tree.
- Skewed binary tree, a binary tree which each node has at most one children.
- Balanced binary tree, a binary tree which has no leaf far from the root.

In code, Binary tree can be first initialized by
struct node{
  int data;
  struct node *left;
  struct node *right;
};

Then, we can start adding a node by adding a function.

struct node* newNode(int data){
  struct node* node = (struct node*)malloc(sizeof(struct node));
  node->data = data;   
  node->left = NULL;
  node->right = NULL;
  return(node);
}
A simple program to first understand Binary Tree

int main(){
  struct node *root = newNode(1);     
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
}
Pertemuan 06 Data Structure, Binary Search Tree (L).
Materi :
- Binary Search Tree
- Binary Search Tree Operations.



Binary Tree Search Tree
Binary Search tree is one kind of data structures that supports faster searching, rapid sorting, and easy insertion & deletion. Binary Tree has three basic operations which consist of find, insert and remove.

  • Find
Begins at root, recursively decided (if X is less than root's key then goes left, if X is more than root's key then goes right, if X equals root's key than it is found.
  • Insert
Begins at root. If X is less than node's key insert into left sub tree. if X is more than node's key, insert into right sub tree. operation is done recursively.
  • Remove
If the key that we want to remove is just a leaf, we just need to delete that node. Well, it starts getting complicated when we need to delete a node which has one child. In this case we need to delete the node an connect it's child to it's parent. When we want to remove a data with two children or more, it need to be done recursively.


I've studied some code for today, which is a simple insertion for binary tree.
#include<stdio.h>
#include<stdlib.h>

struct node{ 
int key; 
struct node *left, *right; 
}; 
struct node *newNode(int item){ 
struct node *temp = (struct node *)malloc(sizeof(struct node)); 
temp->key = item; 
temp->left = temp->right = NULL; 
return temp; 
}
struct node* insert(struct node* node, int key){ 
if (node == NULL)return newNode(key); 
if (key < node->key)node->left = insert(node->left, key); 
else node->right = insert(node->right, key); 
return node; 
}



Comments

Post a Comment

Popular posts from this blog

Rankuman Akhir

Rangkuman Akhir 10 Juni 2020 Nama: Johanes Peter Vincentius NIM: 2301864461 Nama Dosen:Henry Chong(D4460) & Ferdinand Ariandy Luwinda (D4522) Before continuing to my summary, i just want to make a clarification that I did not copas, and if the language is simillar, it's just because I summarize directly from PPT and use a bit of internet for clarification. The point is, I studied while making this summary, sorry if it might have a slight resemblance to the ppt. The summary : Heaps And Tries, both are a data structures algorithm concept In this blog I will be summarizing : Heap Concept Min Heap  Max Heap Min-Max Heap Heap Applications Tries Concept Tries Applications Heap is a complete binary tree which impliments the "heap" property. Heap property ?  Min Heap and Max Heap Min Heap means every node's element is smaller than its children's Max Heap means every node's element is larger than its children's ...
Post a Comment
Read more

Pertemuan III Mengenai pengaplikasian Linked List

Linked List, banyak hal dapat dilakukan dalam linked list, seperti push(insert), pop(delete). memahami konsep Singly Linked List dapat dibilang relatif mudah, namun pengaplikasian kodingnya perlu waktu untuk pemahaman. Saya Johanes Peter akan merangkum apa yang diajarkan di kelas besar pertemuan 3, yaitu mengenai koding linked list. Struct struct Data {     int value;     struct Data *next,*prev; }*head,*curr,*tail; Push tail (insert sebuah data di paling belakang) void push(int a) {     curr = (struct Data*)malloc(sizeof(struct Data));     curr->value = a;     if(head==NULL){         head = tail = curr;     }     else{         tail->next = curr;         curr->prev = tail;         tail = curr;     }     head->prev = tail->next = NULL; } Print isi dalam...
Post a Comment
Read more