Summary Data Structure

Summary

1.Linked List

Definisi Linked List, Single Linked List, Double Linked List, & Circular Linked List

a. Linked List ( LL )

Adalah koleksi data item yang tersusun dalam sebuah barisan  secara linear, dengan penyisipan dan pemindahan dapat dilakukan dalam semua tempat di LL tersebut.

b. Single Linked List

Adalah sebuah LL yang menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan metode LL, suatu daftar isi yang saling berhubungan.

Ilustrasi single LL:

Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LL. Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

c. Double Linked List

Dalam double LL ( Linked List berpointer ganda ) dapat mengatasi kelemahan-kelemahan single LL tersebut.

d. Circular Linked List

Adalah double / single LL yang simpul terakhirnya menunjuk ke simpul awal, dan simpul awalnya menunjuk ke simpul akhir, atau dapat disebut LL yang dibuat seakan-akan

merupakan sebuah lingkaran dengan titik awal dan titik akhir saling bersebelahan jika LL tersebut masih 

2.Stack And Queue

Stack: Elements can be inserted and deleted only from one side of the list, called the top. The insertion of an element is called push operation and the deletion of an element is called pop operation.

Queue: Elements can be inserted only from one side of the list called Rear, and the elements can be deleted only from the other side called the Front. It’s the insertion of an element in a queue is called an Enqueue operation and the deletion of an element is called a Dequeue operation.

3.Hashing Table

Hash Table: Hash table is a method/mechanism of finding a record in a table/list using a key. Suppose we have n record and m key values where m >= n then it for every key if there exist a record n then it a hash table where m is a hash key.

Hash key: Hash key is a unique number which can be converted to a record in a record in a hash table. Here there is a mapping function h(m) which maps each hash key to corresponding records. This function is called hash function.

Hash function: Hash function is a mapping function of hash table which takes the key number as input and gives out the index of the record.

n = h(m) (where m >=n)

Here is a very simple hash function like mod. Suppose we have maximum 10 records. Then we can easily map key to index of record n by mod(m). It directly gives us the record number.

n = mod 10 (m)

hash key, hash function, record index

In a perfect hash table where m >=n there is always record index for a key. When m > n then more than one key may map to a same record. This situation is called hash collision.

Hash collision: If more than one hash key can be mapped to a single record in a hash table then it is called has collision. Example: Say in our example key values ranges from 0 to 9. If we take 10 or more as key then say key m=1 corresponds to record n=1. Now key m=11 also maps to the same record as mod10(11)=1.

4.Binary Search Tree

Binary Search Tree is a binary tree where each node contains a key and an optional associated value. It allows particularly fast lookup, addition, and removal of items.

Binary Search Tree

 Binary Search Tree is a binary tree where each node contains a key and an optional associated value. It allows particularly fast lookup, addition, and removal of items.

The nodes are arranged in a binary search tree according to the following properties:

• The left subtree of a particular node will always contain nodes with keys less than that node’s key.
• The right subtree of a particular node will always contain nodes with keys greater than that node’s key.
• The left and the right subtree of a particular node will also, in turn, be binary search trees.

Time Complexity

In average cases, the above mentioned properties enable the insert, search and deletion operations in $O(log n)$ time where n is the number of nodes in the tree. However, the time complexity for these operations is $O(n)$ in the worst case when the tree becomes unbalanced.

Space Complexity

The space complexity of a binary search tree is $O(n)$ in both the average and the worst cases.

Types of Traversals

The Binary Search Tree can be traversed in the following ways:

1. Pre-order Traversal
2. In-order Traversal
3. Post-order Traversal

The pre-order traversal will visit nodes in Parent-LeftChild-RightChild order.

The in-order traversal will visit nodes in LeftChild-Parent-RightChild order. In this way, the tree is traversed in an ascending order of keys.

The post-order traversal will visit nodes in LeftChild-RightChild-Parent order.