Linked List

Generally a Linked List means "Singly Linked List". It is a chain of records known as Nodes. Each node has at least two members, one of which points to the next Node in the list and the other holds the data.

Figure 1: Singly Linked List

Basically Single Linked Lists are uni-directional as they can only point to the next Node in the list but not to the previous. We use below structure for a Node in our example.

 struct Node
 {
   int Data;
   struct Node *Next;
 }; 

Variable Data holds the data in the Node (It can be a pointer variable pointing to the dynamically allocated memory) while Next holds the address to the next Node in the list.

Figure 2: Node in a Singly Linked List

Head is a pointer variable of type struct Node which acts as the Head to the list. Initially we set 'Head' as NULL which means list is empty.

Basic Operations on a Singly Linked List

• Traversing a List
• Inserting a Node in the List
• Deleting a Node from the List

Traversing a Singly Linked List
Traversing a Singly Linked List is the basic operation we should know before we do other operations like Inserting a Node or Deletion of a Node from the Singly Linked List. Let us see how to traverse Singly Linked List in Figure 1.Let us assume Head points to the first Node in the List.

Pseudocode:

cur = head

forever:

if cur == NULL
break

cur = cur->Next

Complexity:
To traverse a complete list of size 'n' it takes

• Time complexity: O(n).
• Space Complexity: O(1) for storing one temporary variable.

Inserting a Node in Singly Linked List
There are 3 possible cases for inserting a Node in a Singly Linked List.

• Inserting a Node at the beginning of the List
  
  In this case newNode is inserted at the starting of the List. We have to update Next in newNode to point to the previous firstNode and also update Head to point to newNode.
  Pseudocode:

  firstNode = Head->Next
  
  newNode->Next = firstNode
  
  Head->Next = newNode

  But above pseudocode can be modified to reduce the space complexity by removing the temporary variable usage as shown below

  newNode->Next = Head->Next
  
  Head->Next = newNode

  Complexity:
  Time Complexity: O(1)
  Space Complexity: None
  Sourcecode:

  void addBeg(int num)
   {
      struct Node *temp;
  
      temp=(struct Node *)malloc(sizeof(struct Node));
      temp->Data = num;
  
      if (Head == NULL)
      {
         //List is Empty
         Head=temp;
         Head->Next=NULL;
      }
      else
      {
         temp->Next=Head;
         Head=temp;
      }
   }

  
  
• Inserting a Node at the End of the List
  
  In order to add the node at the end of the list we have to first traverse to the end of the List. Then we have to update the Next variable in lastNode pointing to newNode.
  Pseudocode:

  cur = head
  
  forever:
  
   if cur->Next == NULL
   break
  
  cur->Next = newNode

  Complexity:
  To add a Node at the end of a list whose length is 'n'
  
  Time Complexity: O(n)
  Space Complexity: O(1)
  Sourcecode:

  void addEnd(int num)
   {
      struct Node *temp1, *temp2;
  
      temp1=(struct Node *)malloc(sizeof(struct Node));
      temp1->Data=num;
  
      // Copying the Head location into another node.
      temp2=Head;
  
      if(Head == NULL)
      {
         // If List is empty we create First Node.
         Head=temp1;
         Head->Next=NULL;
      }
      else
      {
         // Traverse down to end of the list.
         while(temp2->Next != NULL)
         temp2=temp2->Next;
  
         // Append at the end of the list.
         temp1->Next=NULL;
         temp2->Next=temp1;
      }
   }

  
  
• Inserting a Node at position 'p' in the List
  
  To add at the position 'p' we have to traverse the list until we reach the position 'p'. For this case have to maintain two pointers namely prevNode and curNode. Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position 'p' we have to modify prevNode Next pointing to newNode while newNode points to curNode.
  Pseudocode:

  curNode = head
  curPos = 1
  
  forever:
  
   if curPos == P || curNode == NULL
   break
  
   prevNode = curNode
   curNode = curNode->Next
   curPos++
  
  if curNode != NULL:
   
   prevNode->Next = newNode
   newNode->Next = curNode

  Complexity:
  Time Complexity: O(n) in worst case.
  Space Complexity: O(3)
  Sourcecode:

  void addAt(int num, int loc)
   {
      int i;
      struct Node *temp, *prev_ptr, *cur_ptr;
  
      cur_ptr=Head;
  
      if(loc > (length()+1) || loc <= 0)
      {
         printf("\nInsertion at given location is not possible\n ");
      }
      else
      {
          // If the location is starting of the list
          if (loc == 1)
          {
              addBeg(num);
          }
          else
          {
              for(i=1;i<loc;i++)
              {
                  prev_ptr=cur_ptr;   
                  cur_ptr=cur_ptr->Next;
              }
  
              temp=(struct Node *)malloc(sizeof(struct Node));
              temp->Data=num;
  
              prev_ptr->Next=temp;
              temp->Next=cur_ptr;
          }
      }
   }
  
   // Counting number of elements in the List
  
   int length()
   {
      struct Node *cur_ptr;
      int count=0;
  
      cur_ptr=Head;
  
      while(cur_ptr != NULL)
      {
         cur_ptr=cur_ptr->Next;
         count++;
      }
      return(count);
   }

  A. Leftist Tree
     Leftiest tree diambil dari kata "trie" yang berarti  Retrieval (pengambilan data).
     Leafist Tree adalah:
      1. Merupakan salah satu variasi dari heap yang fungsinya sama yaitu  mencari elemen paling 
          besar atau paling kecil dari tree tersebut.
      2. Leftist tree bermanfaat untuk menggabungkan dua heap menjadi heap tunggal.
        3. Diimplementasikan dengan linked list, karena bukan complete binary tree. 

  
   
   Ada 2 macam leftist tree, yaitu:
  1. Min leftist tree, Setiap node lebih kecil daripada anaknya (min tree). 
  2. Max leftist tree, Setiap node lebih besar dari anaknya(max tree). 

  2. Tries
    •Tries (prefix tree) adalah tree struktur data terstruktur yang digunakan untuk menyimpan array asosiatif (biasanya strings)
  •Kata Trie berasal dari kata Re-TRIE-Val yang berarti trie bisa mencari kata dari kamus hanya dengan prefix dari node tersebut.
  •Tries
   digunakan dalam autocomplete (biasanya ada di mesin pencari, program 
  instant messaging) , dan autocorrect (ada pada program seperti microsoft
   word).
  
  Contoh:     

  Dalam tries berikut tersimpan kata sebagai berikut:
  
  1.ALGO
  2.API
  3.BOM
  4.BOS
  5.BOSAN
  6.BOR

  ---

  Pada leftist tree dikenal istilah x(s), yaitu jarak terdekat dengan eksternal node. Dan x(s) adalah hal  pertama yang diperhatikan kemudian setelah itu beru nilai (value) nya. Untuk mencari jarak terdekat dapat dengan eksternal node nya. Jika lebih tinggi nilai x(s) maka posisi diletakan di bagian kiri.
  Min Leftist Tree dan Max Leftist Tree
  Min leftist tree adalah tree yang node-node paling atas memiliki nilai yang lebih kecil dari node-node yang ada di bawahnya. Jadi, root adalah node dengan nilai terkecil.
  
  
  Contoh min leftist tree adalah:
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Max leftist tree, yakni tree yang node-node paling atas memiliki nilai yang lebih besar dari node-node yang ada di bawahnya. Jadi, root adalah node dengan nilai terbesar.
  Contoh max leftist tree adalah:
  
  
  
  
  
  
  
  
  
  
  
  Ada beberapa operasi yang dapat dilakukan, yaitu:
       1.       insert
       2.      remove min atau max 
       3.       initialize (inisialisasi)
  3. Hashing
  Hashing berasal dari kata "Hash" yang berarti campuran atau kekusutan. Sesuai namanya, hashing digunakan dalam bidang security, khususnya password (kata sandi).
  Hashing dipelajari lebih dalam, dalam bidang security.
  
  Jika ada data yang sama dinamakan tabrakan atau colleisions
  solusi: Linear probing, chaining
  
  linear probing = konsepnya memasukan data yang chainig/violation tsb kedalam array yang masih kosong. Linear probing memiliki keburukan jika terjadi banyak collesions.
  
  Demikianlah materi yang dapat saya sharekan pada hari ini. Semoga materi ini bermanfaat untuk teman-teman (:
  Saya akan kembali membawakan materi pada Sabtu, 7 Juni, karena minggu ini, kuliah ditiadakan (libur)