Linked List, Hash Table & Tree [Theory], Binary Tree [Theory]

RANGKUMAN PEMBELAJARAN UTS SEMESTER 1

LINKED LIST

Linked List (Senarai Berantai) merupakan koleksi elemen linear data yang urutannya tidak teratur dan letak penempatannya ditentukan dengan alokasi memori. Nah, tempat yang kita pesan dari alokasi memori tersebut dinamakan node. Di dalam Linked List ini, kita diperbolehkan untuk memasukan nilai dan menghilangkan nilai elemen di tempat manapun selama itu masih didalam node yang kita punya. Biasanya Linked List ini digunakan di algoritma untuk menyelesaikan Real-Time Problems, dimana jumlah elemen yang dimasukan tidak terduga.

Tapi, terkadang untuk yang sudah mengerti algoritma, akan bertanya-tanya tentang apakah perbedaan antara Linked List sendiri dengan Array ? Berikut adalah penjelesannya.

NO	Linked List	Array
1	Setiap element linked list terdiri dari  bagian, data dan pointer address	Setiap element array hanya berisi data saja
2	Pengalokasian ruang memori dilakukan tanpa pendeklarasian sebelumnya dan terbatas pada jumlah ruang memori yang tersisa (dapat dipakai)	Pengalokasian ruang memori terbatas pada jumlah ruang yang dideklarasikan sebelumnya.

(source : https://kuliahinformatika.wordpress.com/2010/01/21/linked-list-perbedaan-linked-list-dengan-array/)

Nah, mari kita coba membuat sebuah node.. Codingannya adalah sebagai berikut :

Nah, sudah jadi.. tapi waktu di run kalau tidak keluar apa-apa, jangan panik dulu, soalnya kita memang belum memasukan data ke node tersebut.. Bagaimanakah caranya ?

Kita disini melakukan yang Namanya push head.. untuk memasukan data kedalamnya dengan codingan seperti diatas. Push head seperti memasukan node baru, tapi dimasukan dari depan. Ada juga yang Namanya push tail. Push Tail sendiri maksudnya sama seperti push head, tapi dimasukan dari belakang .

              Nah, untuk selanjutnya dimana ada head disitu ada tail. Yep, pushTail. Let’s jump into it.

             

Ada masukan, ada keluarkan.. Yak, Deletion/Pop di data structure ini berguna untuk menghilangkan sebuah node yang kita inginkan.. sama seperti push, pop juga memiliki 2 macam, yaitu pop head dan pop tail.. seperti apa kelanjutannya, mari kita perhatikan codingan berikut ini

Yak, fungsi pop head ini pun adalah untuk menghapus head yang sekarang. Dalam kasus ini, si 456 Budi akan dihapus dari linked list ini dan digantikan kembali oleh 123 Adi. Dalam pop head ini (berlaku juga untuk pop tail) yang pertama kita harus lakukan adalah menyelamatkan head (atau tail) terlebih dahulu baru bisa menghapus head (atau tail) yang lama. Nah, mungkin anda bertanya-tanya mengapa ada free segala, ini kah bukan kek toko beli 1 gratis 1.. bukan. Ini maksudnya untuk membebaskan si alamat yang dipakai oleh 456 Budi agar tidak membuang memori.

Nah bagaimana dengan pop tail ? mari kita simak..

Sama kasusnya seperti pop Head, di pop tail, kita harus menyelamatkan tail nya terlebih dahulu baru membebaskan si tail yang lama. Dalam kasus ini, tail yang awalnya adalah 147 Kali akan dihapus dan digantikan oleh 789 Santi sebagai tail yang baru.

Nah, sekian untuk single linked list hari ini. Sebenarnya masih ada 1 jenis push dan pop, hanya saja saya belum begitu mengerti soal itu, itu akan dibahas di pertemuan berikutnya ya 😊 Maaf jika ada kesalahan, disini kita sama-sama belajar. Jangan toxic sesama pelajar.. Makasihhh and have fun.

=== GOD BLESS ===

HASH TABLE & TREE

INTRODUCTION TO HASH TABLE

Hashing is the process of mapping large amount of data item to smaller table with the help of hashing function. In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.

Advantage using Hash Table : 

• synchronization.
• In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software , particularly for associative arrays, database indexing, caches and sets.

Disadvantages using Hash Table :

• Hash collisions are practically unavoidable. when hashing a random subset of a large set of possible keys.
• Hash tables become quite inefficient when there are many collisions.
• Hash table does not allow null values, like hash map.

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. Some examples of how hashing is used in our lives include:

• In universities, each student is assigned a unique roll number that can be used to retrieve information about them.
• In libraries, each book is assigned a unique number that can be used to determine information about the book, such as its exact position in the library or the users it has been issued to etc.

Hashing is implemented in two steps:

1. An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table.
2. The element is stored in the hash table where it can be quickly retrieved using hashed key.

hash = hashfunc(key)
index = hash % array_size

In this method, the hash is independent of the array size and it is then reduced to an index (a number between 0 and array_size − 1) by using the modulo operator (%).

INTRODUCTION TO TREES

Trees can be defined as a collection of entities called node linked together to stimulate hierarchy. Trees isn’t linear data structure hierarchical structures. Before jump into the explanation, the tree can only walk in 1 direction and cannot go back. For further explanation, let’s look the image below.

As I mentioned earlier, tree only can walk in 1 direction. For example, the node 2 can go to 7, but 7 can’t go back to 2. And it applied to others. That’s it.

There’re so many explanation about the trees. But for make it simple, the trees can be defined same as a Family tree but only a little different from it. There’re things called “Root”, ”Parents”, ”Children”, “Siblings”, “Leaf node” , “Grand Parent & Grand Child”, “Link”, etc. So, let’s jump into the mean all of that.

Root : The top of the trees called “Root”. Root always in the top of tree. It can be filled by any type of data such integer (ex : 2 ), string (ex : name), character (‘a’), etc.

Parent : from the picture above, 2 is a parent from 7 and 5. So, the 2 can be called parent and also 2 can be also called the root of the tree, and so on.

Children : from the picture above, we can see 7 and 5 is a children from 2. And also 2, 10, and 6 is the children from 7 and 9 is a children from 5, and so on.

Sibling : well, from the picture, because 7 and 5 is a child from 2, they can be called siblings because they’re had a same parent. It also applied to 2,10 and 6 as a sibling because they had a same parent is 7. And it applied to the other.

 Leaf Node : the node that hadn’t a child anymore called leaf node. You can see from the picture below that 2,5,11, and 4 are leaf node because they hadn’t a child anymore.

Grand Parent & Grand Child : I don’t know how to put it for definition, but example for grand parent is that 9 is a grand child from 2, and 2 is a grand parent to 9. And it applied to others.

Link : The arrow that connected one to each other called link. Same as the definition, the function from link is to connected each node to other node.

If we can go from node A to B, then A is a ancestors of node B. and B is a descendent to A.

For example, 2,7 and 6 are the ancestors of 11. And 11 is the descendent for 2,7, and 6.

BINARY TREE

BINARY TREE DATA STRUCTURE

              A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

PARTS OF NODE IN BINARY TREE :

1.      Data,

2.      Pointer to left child, and

3.      Pointer to right child.

THE USED FROM BINARY TREE ARE FOLLOWING :

1.      Manipulate hierarchical data,

2.      Make information easy to search,

3.      Manipulate sort list of data,

4.      Composting digital images for visual effect,

5.      Router Algorithms, and

6.       Form of a multi-stage decision-making (see business chess).

TREE’S PART

1.      Root : The topmost node of the tree. The root always placed on very top of tree.

2.      Children : The element directly under a root. Like the above there said, the tree HAVE the most 2 children. As long they have 2 children, they can be called TREE.

There are a common properties in tree we’ve should known about it. The common properties is the maximum number of nodes at level ‘l’ where ‘l’ is a root of binary tree is . For example, lets take a number for ‘l’ is 1 and we input the 1 into the formula, we can get 2 of the maximum nodes. And the other child below the nodes can be calculate by 2*.

The next common property is maximum number of nodes in a binary tree of height ‘h’ is  . This is a simple geometric series with h terms and sum of this series is 2^h – 1. In some books, height of the root is considered as 0. In this convention, the above formula becomes 2^h+1 – 1.

TYPE OF BINARY TREE

1.      Full Binary Tree 

A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children.

2.     Complete Binary Tree

A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

3.     Perfect Binary Tree 

A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

4.     Balanced Binary Tree

A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, AVL tree maintains O(Log n) height by making sure that the difference between heights of left and right subtrees is at most 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths are same and there are no adjacent red nodes. Balanced Binary Search trees are performance wise good as they provide O(log n) time for search, insert and delete.

5.     A degenerate (or pathological) tree

 A Tree where every internal node has one child. Such trees are performance-wise same as linked list.

           

            For further information about Binary Tree, there are following source that I take for this document.

            Sources :

https://www.geeksforgeeks.org/binary-tree-data-structure/

https://www.geeksforgeeks.org/binary-tree-data-structure/#Introduction

https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/