Double Linked List

Double Link List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau belakang.

Elemen double link list terdiri dari tiga bagian:

- Bagian data informasi

- Pointer next yang menunjuk ke elemen berikutnya

- Pointer prev yang menunjuk ke elemen sebelumnya

Untuk menunjuk head dari double link list, pointer prev dari elemen pertama menunjuk NULL. Sedangkan untuk menunjuk tail, pointer next dari elemen terakhir menunjuk NULL.

Contoh Membuat TDA(Tipe Data Abstrak) dari Double Linked Circular List tersebut.

Instan :

Double Linked Circular List

Operasi :

Buat_node(char x) : membuat node baru dengan informasi x

Tambah_elemen_didepan() : menambah elemen paling depan (pointernya menunjuk

elemen pertama link list)

Tambah_elemen_dibelakang() : menambah elemen paling belakang (pointer elemen

yang baru menunjuk elemen pertama)

Hapus_elemen_() : Menghapus elemen (pointer menunjuk elemen yang akan dihapus)

Cetak () : menelusuri elemen satu demi dan menampilkan informasinya.

Ada 2 jenis Double Linked List yaitu :

•         Double Linked List Circular

•         Double Linked List Non Circular

1.     Double Linked List Circular

Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu:

1 field pointer yang menunjuk pointer berikutnya “next“,

1 field menunjuk pointer sebelumnya ” prev “,

1 field yang berisi data untuk node tersebut .

Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC

Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya

Untuk pembentukan node baru , mulanya pointer next dan prev akan menunjuk ke nilai NULL

Selanjutnya pointer prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.

2.     Double Linked List Non Circular

DLLNC "Double linked list non circular" adalah Double Linked List yang memiliki 2 buah pointer yaitu pointer next dan prev.

Pointer next menunjuk pada node setelahnya dan pointer prev menunjuk pada node sebelumnya.

Pengertian:

Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya.

Linked List : artinya node-node tersebut saling terhubung satu sama lain.

Non Circular : artinya pointer prev dan next-nya akan menunjuk padaNULL.

Ilustrasi DLLNC

Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya & ke node sebelumnya

Untuk pembentukan node baru , mulanya pointer next dan prev akan menunjuk ke nilai NULL

Selanjutnya pointer prev akan menunjuk ke node sebelumnya , dan pointer next akan menunjuk ke node selanjutnya pada list.

Deklarasi dan node baru DLLNC

Deklarasi node

Dibuat dari struct berikut ini :

typedef struct TNode {

int data ;

TNode *next ;

Tnode * prev ;

};

Pembentukan node baru

Digunakan keyword new yang berarti mempersiapkan sebuah node baru berserta alokasi memorinya .

TNode * baru ;

baru = new TNode ;

baru ->data = databaru ;

baru ->next = NULL;

baru -> prev = NULL; 

Berikut saya lampirkan satu contohnya:

#include <iostream>

using namespace std;

template <class T>

struct Node

{

  T data;

  Node * next;

  Node(T data) : data(data), next(NULL) {}

};

template <class T>

class CircularLinkedList

{

public:

  CircularLinkedList() : head(NULL) {}

  ~CircularLinkedList();

  void addNode(T data);

  void deleteNode(T data);

  template <class U>

  friend std::ostream & operator<<(std::ostream & os, const CircularLinkedList<U> & cll);

private:

  Node<T> * head;

};

template <class T>

CircularLinkedList<T>::~CircularLinkedList()

{

  if (head)

    {

      Node<T> * tmp = head;

      while (tmp->next != head)

        {

          Node<T> * t = tmp;

          tmp = tmp->next;

          delete(t);

        }

      delete tmp;

      head = NULL;

    }

}

template <class T>

void CircularLinkedList<T>::addNode(T data)

{

  Node<T> * t = new Node<T>(data);

  if (head == NULL)

    {

      t->next = t;

      head = t;

      return;

    }

  Node<T> * tmp = head;

  while (tmp->next !=  head)

    {

      tmp = tmp->next;

    }

  tmp->next = t;

  t->next = head;

}

template <class T>

void CircularLinkedList<T>::deleteNode(T data)

{

  Node<T> * tmp = head;

  Node<T> * prev = NULL;

  while (tmp->next !=  head)

    {

      if (tmp->data == data) break;

      prev = tmp;

      tmp = tmp->next;

    }

  if (tmp == head)

    {

      while (tmp->next != head)

        {

          tmp = tmp->next;

        }

      tmp->next = head->next;

      delete head;

      head = tmp->next;

    }

  else

    {

      prev->next = tmp->next;

      delete tmp;

    }

}

template <class U>

std::ostream & operator<<(std::ostream & os, const CircularLinkedList<U> & cll)

{

  Node<U> * head = cll.head;

  if (head)

    {

      Node<U> * tmp = head;

      while (tmp->next != head)

        {

          os << tmp->data << " ";

          tmp = tmp->next;

        }

      os << tmp->data;

    }

  return os;

}

int main()

{

  CircularLinkedList<int> cll;

  cll.addNode(1);

  cll.addNode(2);

  cll.addNode(3);

  cll.addNode(4);

  cll.addNode(5);

  cout << cll << endl;

  cll.deleteNode(3);

  cll.deleteNode(1);

  cll.deleteNode(5);