review before mid

1.Linked List

What is Linked List:

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have the following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.

Advantages vs Disadvantages of Linked List?

Advantages of Linked List

Dynamic Data Structure

Linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memeory. So there is no need to give initial size of linked list.

Insertion and Deletion

Insertion and deletion of nodes are really easier. Unlike array here we don’t have to shift elements after insertion or deletion of an element. In linked list we just have to update the address present in next pointer of a node.

No Memory Wastage

As size of linked list can increase or decrease at run time so there is no memory wastage. In case of array there is lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements are wasted. There is no such problem in linked list as memory is allocated only when required.

Implementation

Data structures such as stack and queues can be easily implemented using linked list.

Disadvantages of Linked List

Memory Usage

More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself.

Traversal

Elements or nodes traversal is difficult in linked list. We can not randomly access any element as we do in array by index. For example if we want to access a node at position n then we have to traverse all the nodes before it. So, time required to access a node is large.

Reverse Traversing

In linked list reverse traversing is really difficult. In case of doubly linked list its easier but extra memory is required for back pointer hence wastage of memory.

There are types of Linked List, which is :

- Singly Linked List

It is the most common. Each node has data and a pointer the next code

- Doubly Linked List

Add a pointer to the previous node in a doubly-linked list. Thus, we can go in either direction, forward and backward

- Circular Singly Linked List

The last node contains a pointer to the first node. We can have a circular singly linked list as well as a circular doubly linked list. There is no storing of NULL values in the list

- Circular Doubly Linked List

It is similar to a circular single linked list, but the total pointer in each node here is two pointers. The more complex type of data structure in which a node contains pointers to its previous node as well to the next node. The circular doubly linked list doesn't contain NULL in any of the nodes. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.

2.Binary Tree

APA ITU BINARY TREE

Seperti kata binary yaitu dua,binary tree adalah pohon yang memiliki dua cabang.Pohon ini digunakan dalam mengatur data agar mudah dicari dan dihapus.

APA FUNGSI BINARY TREE DAN CONTOH BINARY TREE

Binary tree digunakan untuk mengurutkan jumlah data yang banyak agar dapat dicari dan dihapus dengan mudah.Binary tree merupakan teori dasar untuk memudahkan penyusunan data agar lebih tertata.Contoh binary tree seperti ini:


  
Binary tree diatas dibuat dengan program jika lebih besar dari atasnya akan berpindah ke kanan dan jika lebih kecil dari angka yang diatasnya akan berpindah ke kiri.
Misalkan A adalah 5,B akan berisikan angka yang lebih kecil dari 5 dan C akan berisikan angka jika lebih besar dari 5.Begitu pula B dan C sistemnya akan sama dengan A

3.Hash Table

Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa.

Hash Function

Fungsi hash adalah fungsi apa pun yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash.

Untuk mencapai mekanisme hashing yang baik, penting untuk memiliki fungsi hash yang baik dengan persyaratan dasar berikut:

1. Mudah dikomputasi: Seharusnya mudah dikomputasi dan tidak harus menjadi algoritma itu sendiri.
2. Distribusi seragam: Ini harus menyediakan distribusi seragam di seluruh tabel hash dan tidak boleh menghasilkan pengelompokan.
3. Kurang tabrakan: Tabrakan terjadi ketika pasangan elemen dipetakan ke nilai hash yang sama. Ini harus dihindari.

Hash Table



Tabel hash adalah struktur data yang digunakan untuk menyimpan pasangan kunci / nilai. Ini menggunakan fungsi hash untuk menghitung indeks ke dalam array di mana elemen akan dimasukkan atau dicari. Dengan menggunakan fungsi hash yang baik, hashing dapat bekerja dengan baik. Di bawah asumsi yang masuk akal, waktu rata-rata yang diperlukan untuk mencari elemen dalam tabel hash adalah O (1).