Daftar Tertaut (Linked List)

Indonesian (Bahasa Indonesia) translation by Danish Kalesaran (you can also view the original English article)

Struktur data pertama yang akan kita pelajari adalah Daftar Tertaut, dan ini bukan tanpa alasan. Selain merupakan struktur yang ada hampir di mana saja mulai dari sistem operasi sampai video game, struktur ini juga merupakan dasar untuk membangun banyak struktur data lainnya.

Ikhtisar

Dalam pemahaman yang sangat luas, tujuan dari daftar tertaut adalah untuk menyediakan mekanisme yang konsisten untuk menyimpan dan mengakses sejumlah data yang terpisah. Itu dilakukan dengan menghubungkan datanya ke dalam daftar.

Sebelum kita masuk ke dalam artinya, mari kita mulai dengan meninjau bagaimana data disimpan di dalam satu array.

Data integer disimpan di dalam satu array

Seperti yang ditampilkan di gambar, data array disimpan sebagai satu potong memori yang teralokasi secara berurutan yang terbagi secara logis. Data yang disimpan di dalam array ditempatkan di dalam salah satu dari bagian-bagian itu dan dirujuk dengan lokasinya atau indeksnya di dalam array.

Ini adalah cara yang baik untuk menyimpan data. Kebanyakan bahasa pemrograman memudahkan kegiatan alokasi array dan operasi pada konten dari array itu. Penyimpanan data yang berurutan memberikan keuntungan secara performa (yaitu lokalitas data), kemudahan dalam melakukan iterasi pada data, dan data itu bisa diakses secara langsung melalui indeksnya (akses acak) secara konstan.

Tapi ada saat di mana array bukanlah solusi yang ideal.

Misalnya program yang memiliki tuntutan sebagai berikut:

Baca integer dengan jumlah yang tidak diketahui dari sumber input (method NextValue) hingga bilangan 0xFFFF ditemui.
Sampaikan semua integer yang sudah dibaca (dalam sekali pemanggilan) ke method ProcessItems.

Karena tuntutan dari program itu mengindikasikan bahwa beberapa value harus disampaikan ke method ProcessItems dalam satu pemanggilan, satu solusi yang paling jelas adalah menggunakan array integer. Contohnya:

void LoadData()
{
	// Asumsikan bahwa 20 sudah cukup untuk menampung nilainya.
	int[] values = new int[20];
	for (int i = 0; i < values.Length; i++)
	{
		if (values[i] == 0xFFFF)
		{
			break;
		}

		values[i] = NextValue();
	}

	ProcessItems(values);
}

void ProcessItems(int[] values)
{
	// ... Proses data.
}

Solusi ini memiliki beberapa kendala, tapi yang paling kentara adalah ketika menerima lebih dari 20 nilai. Dalam program itu sekarang, nilai dari 21 sampai n diabaikan begitu saja. Ini bisa diringankan dengan mengalokasikan lebih dari 20 nilai, mungkin 200 atau 2000. Mungkin ukurannya bisa dikonfigurasi oleh user, atau jika arraynya sudah penuh array yang lebih besar bisa dialokasikan dan semua data sudah ada dikopi ke situ. Pada akhirnya solusi-solusi itu menciptakan kerumitan dan membuang memori.

Apa yang kita perlukan adalah kumpulan yang memampukan kita untuk menambahkan sejumlah integer yang tidak ditentukan kemudian melakukan enumerasi terhadap integer-integer itu sesuai urutan masuknya masing-masing integer. Ukuran maksimum dari kumpulan itu tidak ditentukan dan indeksasi untuk akses acak bukanlah keharusan. Untuk itu kita perlu daftar tertaut.

Sebelum kita melanjutkan dan mempelajari bagaimana daftar tertaut dirancang dan diterapkan, kita tinjau dulu solusi akhir kita.

static void LoadItems()
{
	LinkedList list = new LinkedList();
	while (true)
	{
		int value = NextValue();
		if (value != 0xFFFF)
		{
			list.Add(value);
		}
		else
		{
			break;
		}
	}

	ProcessItems(list);
}

static void ProcessItems(LinkedList list)
{
		// ... Proses data.
}

Perhatikan bahwa semua kendala dari solusi dengan array yang sebelumnya tidak lagi ada. Persoalan array yang tidak cukup besar atau pengalokasian yang lebih banyak dari yang diperlukan tidak ada lagi.

Anda juga harus menyadari beberapa keputusan desain yang akan kita buat nanti yang diungkapkan oleh solusi ini, yaitu bahwa class LinkedList menerima argumen dengan tipe yang generik dan menerapkan interface IEnumerable.

Menerapkan Class LinkedList

Node

Inti dari struktur data daftar tertaut adalah class Node. Suatu node adalah wadah yang menyediakan kemampuan untuk menyimpan data dan berhubungan dengan node yang lain.

Dalam bentuknya yang paling sederhana, satu class Node yang memuat integer bisa berbentuk seperti ini:

public class Node
{
	public int Value { get; set; }
	public Node Next { get; set; }
}

Dengan ini kita bisa menciptakan daftar tertaut yang sangat sederhana. Pada contoh berikut, kita akan mengalokasikan tiga node (first, middle, dan last) dan kemudian menautkan semuanya ke dalam satu daftar.

1	// +-----+------+
2	// \| 3 \| null +
3	// +-----+------+
4	Node first = new Node { Value = 3 };
5
6	// +-----+------+ +-----+------+
7	// \| 3 \| null + \| 5 \| null +
8	// +-----+------+ +-----+------+
9	Node middle = new Node { Value = 5 };
10
11	// +-----+------+ +-----+------+
12	// \| 3 \| *---+--->\| 5 \| null +
13	// +-----+------+ +-----+------+
14	first.Next = middle;
15
16	// +-----+------+ +-----+------+ +-----+------+
17	// \| 3 \| *---+--->\| 5 \| null + \| 7 \| null +
18	// +-----+------+ +-----+------+ +-----+------+
19	Node last = new Node { Value = 7 };
20
21	// +-----+------+ +-----+------+ +-----+------+
22	// \| 3 \| ---+--->\| 5 \| ---+-->\| 7 \| null +
23	// +-----+------+ +-----+------+ +-----+------+
24	middle.Next = last;

Sekarang kita memiliki daftar tertaut yang dimulai dengan node first dan diakhiri dengan node last property Next untuk node last mengarah pada null yang merupakan penanda akhir dari daftar (end-of-list). Dengan daftar ini, kita bisa melakukan operasi dasar. Misalnya, nilai dari property Data dari masing-masing node:

private static void PrintList(Node node)
{
	while (node != null)
	{
		Console.WriteLine(node.Value);
		node = node.Next;
	}
}

Cara kerja dari method PrintList adalah melakukan iterasi terhadap tiap node di dalam daftar itu, menampilkan nilai dari node yang kini, kemudian berpindah ke node yang dirujuk oleh property Next.

Dengan pemahaman terhadap perkiraan bentuk dari node daftar tertaut, mari kita lihat class LinkedListNode yang sebenarnya.

public class LinkedListNode
{
	/// 
	/// Bentuk node baru dengan nilai yang ditentukan.
	/// 
	public LinkedListNode(T value)
	{
		Value = value;
	}

	/// 
	/// Nilai dari node.
	/// 
	public T Value { get;  internal set; }

	/// 
	/// Node yang berikutnya dalam daftar tertaut (null jika merupakan node terakhir).
	/// 
	public LinkedListNode Next { get;  internal set; }
}

Class LinkedList

Sebelum menerapkan class LinkedList, kita perlu memikirkan apa yang kita harapkan dari daftar itu.

Sebelumnya kita sudah melihat bahwa kumpulan itu harus bisa mendukung data dengan tipe yang ditentukan jadi kita tahu yang kita inginkan adalah menciptakan interface yang generik.

Karena kita menggunakan framework .NET untuk menerapkan daftar itu, maka wajar jika kita ingin class itu untuk bisa bertindak sebagaimana tipe data kumpulan lainnya yang sudah ada di dalam framework. Cara termudah untuk melakukan ini adalah menerapkan interface ICollection<T>. Perhatikan bahwa saya memilih ICollection<T> bukannya IList<T>. Ini karena interface IList<T> memberikan kemampuan untuk mengakses nilai berdasarkan indeks. Pengindeksan secara langsung biasanya berguna tapi tidak bisa diterapkan secara efisien di dalam daftar tertaut.

Dengan mengetahui persyaratan ini kita bisa menciptakan dasar dari class, kemudian melengkapi method-method ini nanti.

public class LinkedList : 
	System.Collections.Generic.ICollection
{
	public void Add(T item)
	{
		throw new System.NotImplementedException();
	}

	public void Clear()
	{
		throw new System.NotImplementedException();
	}

	public bool Contains(T item)
	{
		throw new System.NotImplementedException();
	}

	public void CopyTo(T[] array, int arrayIndex)
	{
		throw new System.NotImplementedException();
	}

	public int Count
	{
		get;
		private set;
	}

	public bool IsReadOnly
	{
		get { throw new System.NotImplementedException(); }
	}

	public bool Remove(T item)
	{
		throw new System.NotImplementedException();
	}

	public System.Collections.Generic.IEnumerator GetEnumerator()
	{
		throw new System.NotImplementedException();
	}

	System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
	{
		throw new System.NotImplementedException();
	}
}

Add

Perilaku	Menambahkan nilai yang disediakan ke akhir dari daftar tertaut.
Performa	0(1)

Menambhkan sebuah item pada sebuah linked list melibatkan tiga langkah:

Alokasikan instans LinkedListNode yang baru.
Temukan node terakhir dari daftar yang ada.
Arahkan properti Next dari node terakhir ke node yang baru.

Intinya adalah mengetahui node mana yang merupakan node terakhir di dalam daftar. Ada dua cara bagi kita untuk mengetahui ini. Yang pertama adalah mengawasi node yang pertama (node "head") dan menelusuri daftar sampai kita menemukan node terakhir. Pendekatan ini tidak mengharuskan kita untuk mengawasi node yang terakhir, yang menyimpan memori sebesar satu rujukan (apapun ukuran dari platform pointer anda), tapi mengharuskan kita untuk menjalani daftar setiap kali node yang baru ditambahkan. Ini akan membuat Add menjadi operasi 0(n).

Pendekatan yang kedua adalah menjejaki node terakhir (node "tail") di dalam daftar dan ketika kita menambahkan node yang baru kita hanya perlu mengakses rujukan yang sudah kita simpan secara langsung. Ini merupakan algoritma 0(1), dan dengan begitu merupakan pendekatan yang lebih disukai.

Hal pertama yang perlu kita lakukan adalah menambahkan dua field private ke class LinkedList: rujukan kepada node yang pertama (kepala) dan node yang terakhir (tail).

1	private LinkedListNode _head;
2	private LinkedListNode _tail;

Kemudian kita perlu menambahkan method yang menjalankan tiga langkah yang tadi.

public void Add(T value)
{
	LinkedListNode node = new LinkedListNode(value);
	
	if (_head == null)
	{
		_head = node;
		_tail = node;
	}
	else
	{
		_tail.Next = node;
		_tail = node;
	}
	
	Count++;
}

Yang pertama adalah melakukan alokasi instans LinkedListNode yang baru. Kemudian memeriksa apakah daftar itu kosong. Jika daftar itu kosong, node yang baru ditambahkan dengan memasukkan rujukan _head dan _tail ke node yang baru. Node yang baru itu sekarang merupakan node yang pertama dan kedua dalam daftar. Jika daftar itu tidak kosong, node itu ditambahkan ke akhir dari daftar dan rujukan _tail diperbarui untuk merujuk pada akhir yang baru dari daftar.

Properti Count dinaikkan ketika suatu node ditambahkan untuk memastikan properti ICollection<T>. Count mengembalikan nilai yang akurat.

Remove

Perilaku	Menghapus node pertama di daftar yang nilainya sama dengan nilai yang diberikan. Method ini mengembalikan true jika ada nilai yang dihapus. Jika tidak ada maka yang dikembalikan adalah false.
Performa	O(n)

Sebelum kita lanjut dengan algoritma Remove, mari kita tinjau apa yang hendak diselesaikannya. Ada empat node di dalam daftar pada daftar berikut. Kita hendak menghapus node yang bernilai tiga.

Ketika penghapusan sudah dilakukan, daftar itu akan dimodifikasi sehingga properti Next pada node yang bernilai dua mengharah pada node yang bernilai empat.

Algoritma dasar untuk penghapusan node adalah:

Temukan node yang akan dihapus.
Perbarui properti Next dari node yang mendahului node yang dihapus untuk mengarah pada node setelah node yang dihapus.

Seperti biasanya, yang sulit adalah detailnya. Ada beberapa situasi yang harus kita pertimbangkan ketika menghapus suatu node:

Daftar bisa saja kosong, atau nilai yang hendak kita hapus bisa saja tidak ada di dalam daftar. Dalam situasi ini daftar itu tidak akan berubah.
Node yang akan dihapus bisa saja merupakan satu-satunya node di dalam daftar. Dalam situasi ini kita hanya perlu mengatur field _head dan _tail menjadi null.
Node yang akan dihapus bisa saja merupakan node yang pertama. Dalam situasi ini tidak ada node sebelum node ini, jadi kita perlu memperbarui field _head untuk mengarah pada node head yang baru.
Node itu bisa saja berada di tengah daftar.
Node itu bisa saja merupakan node terakhir di daftar. Dalam situasi ini kita perbarui field _tail untuk merujuk pada node kedua dari belakang dalam daftar dan mengatur properti Next-nya menjadi null.

public bool Remove(T item)
{
	LinkedListNode previous = null;
	LinkedListNode current = _head;
	
	// 1: Daftar kosong: Jangan lakukan apa-apa.
	// 2. Node tunggal: Jadikan nilai sebelumnya null.
	// 3: Node banyak:
	//		a: Node yang hendak dihapus adalah node pertama.
	// 		b: Node yang hendak dihapus ada di tengah atau di akhir.
	
	while (current != null)
	{
		if (current.Value.Equals(item))
		{
			// Ini adalah node di tengah atau di akhir.
			if (previous != null)
			{
				// Situasi 3b.
				
				// Sebelum: Head -> 3 -> 5 -> null
				// Sesudah: Head -> 3 ------> null
				previous.Next = current.Next;
				
				// Node terakhir, jadi perbarui _tail.
				if (current.Next == null)
				{
					_tail = previous;
				}
			}
			else
			{
				// Situasi 2 atau 3a.
				
				// Sebelum: Head -> 3 -> 5
				// Sesudah: Head ------> 5
				
				// Head -> 3 -> null
				// Head ------> null
				_head = _head.Next;
				
				// Apakah daftarnya sekarang kosong?
				if (_head == null)
				{
					_tail = null;
				}
			}
			Count--;
			
			return true;
		}
		
		previous = current;
		current = current.Next;	
	}
	
	return false;
}

Properti Count dikurangi ketika suatu node dihapus untuk memastikan properti ICollection<T>. Count mengembalikan nilai yang akurat.

Contains

Perilaku	Mengembalikan Boolean yang mengindikasikan apakah nilai yang diberikan ada di dalam daftar tertaut.
Performa	O(n)

Method Contains cukup sederhana. Dia melihat ke setiap node dalam daftar, dari yang pertama hingga yang terakhir, dan mengembalikan true ketika suatu node yang cocok dengan parameter sudah ditemukan. Jika akhir dari daftar ditemukan dan node tidak ditemukan, method ini mengembalikan false.

public bool Contains(T item)
{
	LinkedListNode current = _head;
	while (current != null)
	{
		if (current.Value.Equals(item))
		{
			return true;
		}
		
		current = current.Next;
	}
	
	return false;
}

GetEnumerator

Perilaku	Mengembalikan satu instans dari IEnumerator yang memampukan untuk enumerasi terhadap nilai dari daftar tertaut dari pertama hingga terakhir.
Performa	Mengembalikan instans dari enumerator adalah operasi O(1). Melakukan enumerasi terhadap setiap item adalah operasi O(n).

GetEnumerator diterapkan dengan melakukan enumerasi terhadap daftar dari node pertama hingga terakhir dan menggunakan keyword C# yield untuk mengembalikan nilai dari node yang sekarang pada pengguna.

Perhatikan bahwa LinkedList menerapkan perilaku iterasi di dalam versi IEnumerable<T> dari method GetEnumerator dan mengikuti perilaku ini dalam versi IEnumerable.

IEnumerator IEnumerable.GetEnumerator()
{
	LinkedListNode current = _head;
	while (current != null)
	{
		yield return current.Value;
		current = current.Next;
	}
}

IEnumerator IEnumerable.GetEnumerator()
{
	return ((IEnumerable)this).GetEnumerator();
}

Clear

Perilaku	Menghapus semua item dari daftar.
Performa	O(1)

Method Clear mengatur field _head dan _tail ke null untuk membersihkan daftar. Karena .NET memiliki garbage collector, node-node itu tidak harus dihapus secara eksplisit. Memastikan bahwa jika node memuat rujukan IDisposable maka harus dibuang bukanlah tanggung jawab dari daftar tertaut tapi dari pengguna.

public void Clear()
{
	_head = null;
	_tail = null;
	Count = 0;
}

CopyTo

Perilaku	Mengkopi isi dari daftar tertaut dari awal hingga akhir ke dalam array yang disediakan, dimulai dari index array yang ditentukan.
	Performa	O(n)

Method CopyTo melakukan iterasi terhadap isi dari daftar dan menggunakan penempatan sederhana untuk mengkopi item ke array. Memastikan array sasaran untuk memiliki ruangan kosong yang cukup untuk memuat semua item dalam daftar merupakan tanggung jawab dari pengguna.

public void CopyTo(T[] array, int arrayIndex)
{
	LinkedListNode current = _head;
	while (current != null)
	{
		array[arrayIndex++] = current.Value;
		current = current.Next;
	}
}

Count

Perilaku	Mengembalikan sebuah integer yang mengindikasikan jumlah item yang ada di dalam daftar. Jika daftar itu kosong, maka nilai yang dikembalikan adalah 0.
Performa	O(1)

Count hanyalah properti yang diterapkan secara otomatis dengan getter publick dan setter private. Perilaku yang sebenarnya terjadi di dalam method Add, Remove, dan Clear.

public int Count
{
	get;
	private set;
}

IsReadOnly

Perilaku	Mengembalikan false jika daftar itu tidak read-only.
Performa	O(1)

1	public bool IsReadOnly
2	{
3	get { return false; }
4	}

Daftar Tertaut Ganda

Class LinkedList yang baru kita buat dikenal sebagai daftar tertaut tunggal. Ini berarti hanya ada terdapat satu tautan searah di antara satu node dan node berikutnya di dalam daftar. Ada variasi yang umum dari daftar tertaut yang memampukan pengguna untuk mengakses daftar tertaut dari dua arah. Variasi ini dikenal sebagai daftar tertaut ganda.

Untuk menciptakan daftar tertaut ganda pertama kita harus memodifikasi class LinkedListNode kita untuk memiliki satu properti baru yang bernama Previous. Previous berlaku seperti Next tapi mengarah pada node sebelumnya di dalam daftar.

Daftar tertaut ganda yang menggunakan properti node Previous

Seksi berikut akan menjelaskan perubahan dari daftar tertaut tunggal dan daftar tertaut ganda.

Class Node

Satu-satunya perubahan terhadap class LinkedListNode adalah penambahan properti baru yang bernama Previous yang mengarah pada LinkedListNode yang sebelumnya di dalam daftar tertaut, atau mengembalikan null jika merupakan node pertama dalam daftar.

public class LinkedListNode
{
	///
	/// Bentuk node baru dengan nilai yang diberikan
	///
	///
	public LinkedListNode(T value)
	{
		Value = value;
	}
	
	///
	/// Nilai dari node.
	///
	public T Value { get; internal set; }
	
	///
	/// Node berikutnya dalam daftar tertaut (null jika node terakhir)
	///
	public LinkedListNode Next { get; internal set; }
	
	///
	/// Node sebelumnya dalam linked list (null jika node pertama)
	///
	public LinkedListNode Previous { get; internal set; }
}

Add

Sementara daftar tertaut tunggal hanya menambahkan node ke akhir dari daftar, daftar tertaut ganda bisa menambahkan node ke awal dan akhir dari daftar dengan menggunakan AddFirst dan AddLast. Method ICollection<T>. Add akan mengikuti method AddLast untuk mempertahankan kompatibilitas dengan class List dari daftar tertaut tunggal.

AddFirst

Perilaku	Menambahkan nilai yang diberikan ke depan daftar.
Performa	O(1)

Menambahkan node ke depan daftar sangat mirip dengan menambahkan node ke daftar tertaut tunggal.

Set properti Next dari node yang baru ke node head yang lama.
Set properti Previous dari node head yang lama ke node yang baru.
Perbarui field _tail (jika diperlukan) dan tambahkan Count.

public void AddFirst(T value)
{
	LinkedListNode node = new LinkedListNode(value);
	
	// Simpan dulu head node yang lama supaya tidak hilang.
	LlinkedListNode temp = _head;
	
	// Arahkan head ke node yang baru.
	_head = node;
	
	// Masukkan sisa dari daftar ke belakang head.
	_head.Next = temp;
	
	if (Count == 0)
	{
		// Jika daftar kosong maka head dan tail harus
		// merujuk pada node yang baru.
		_tail = _head;
	}
	else
	{
		// Sebelum: head -------> 5 <-> 7 -> null
		// Sesudah: head -> 3 <-> 5 <-> 7 -> null
		temp.Previous = head;
	}
	
	Count++;
}

AddLast

Perilaku	Menambahkan nilai yang diberikan ke akhir dari daftar.
Performa	O(1)

Menambahkan node ke akhir dari daftar lebih mudah daripada menambahkan node ke awal daftar.

Node yang baru hanya perlu ditambahkan ke akhir dari daftar, perbarui state dari _tail dan _head sebagaimana diperlukan, dan Count ditambahkan.

public void AddLast(T value)
{
	LinkedListNode node = new LinkedListNode(value);
	
	if (Count == 0)
	{
		_head = node;
	}
	else
	{
		_tail.Next = node;
		
		// Sebelum: Head -> 3 <-> 5 -> null
		// Sesudah: Head -> 3 <-> 5 <-> 7 -> null
		// 7.Previous = 5
		node.Previous = _tail;
	}
	
	_tail = node;
	Count++;
}

Seperti sudah disebutkan sebelumnya, ICollection<T>.Add sekarang hanya akan memanggil AddLast.

1	public void Add(T value)
2	{
3	AddLast(value);
4	}

Remove

Seperti method Add, method Remove akan dimampukan untuk menghapus node dari awal atau akhir dari daftar. Perubahan pada method ICollection<T>.Remove adalah bisa memperbarui properti Previous yang seharusnya.

RemoveFirst

Perilaku	Menghapus nilai pertama dari daftar. Jika daftar itu kosong, tidak ada yang perlu dilakukan. Mengembalikan true jika ada nilai yang dihapus. Jika tidak maka mengembalikan false.
Performa	O(1)

RemoveFirst membarui daftar dengan menentukan property head dari daftar tertaut menjadi node kedua dalam daftar itu dan membarui property Previous-nya ke null. Ini menghapus semua rujukan ke node head sebelumnya, menghapusnya dari daftar. Jika daftar itu hanya memuat satu singleton, atau kosong, daftar itu akan menjadi kosong (property head dan tail akan menjadi null).

public void RemoveFirst()
{
  if (Count != 0)
  {
    // Sebelum: Head -> 3 <-> 5
    // Sesudah: Head -------> 5
    
    // Head -> 3 -> null
    // Head -------> null
    _head = _head.Next;
    
    Count--;
    
    if (Count == 0)
    {
      _tail = null;
    }
    else
    {
      // 5.Previous was 3; now it is null.
      _head.Previous = null;
    }
  }
}

RemoveLast

Perilaku	Menghapus node terakhir dari daftar. Jika daftar kosong, tidak ada yang dilakukan. Mengembalikan true jika satu nilai dihapus. Jika tidak ada nilai yang dihapus maka yang dikembalikan adalah false.
Performa	O(1)

RemoveLast

bekerja dengan cara menetapkan property tail dari daftar menjadi node sebelum node tail yang sekarang. Ini menghapus node terakhir dari daftar. Jika daftar itu kosong atau hanya memiliki satu node, ketika method ini mengembalikan property head dan tail, mereka akan menjadi null.

public void RemoveLast()
{
  if (Count != 0)
  {
    if (Count == 1)
    {
      _head = null;
      _tail = null;
    }
    else
    {
      // Sebelum: Head --> 3 --> 5 --> 7
      //          Tail = 7
      // Sesudah: Head --> 3 --> 5 --> null
      //          Tail = 5
      // Null-kan property Next dari 5
      tail.Previous.Next = null;
    }
    
    Count--;
  }
}

Remove

Perilaku	Menghapus node pertama dari dalam daftar yang nilainya sama dengan nilai yang diberikan. Method ini mengembalikan true jika ada satu nilai yang dihapus, dan jika tidak ada maka yang dikembalikan adalah false.
Performa	O(n)

Method ICollection<T>Remove hampir identik dengan versi yang tertaut tunggal tapi property Previous sekarang diperbarui dalam operasi penghapusan. Untuk menghindari perulangan kode, method ini memanggil RemoveFirst ketika sudah diketahui bahwa node yang akan dihapus adalah node pertama di dalam daftar.

public bool Remove(T item)
{
  LinkedListNode previous = null;
  LinkedListNode current = head;l
  
  // 1: Daftar kosong: Tidak ada yang dilakukan.
  // 2: Node tunggal: Null-kan previous.
  // 3: Node banyak:
  //    a: Node yang akan dihapus adalah node pertama.
  //    b: Node yang akan dihapus adalah yang tengah atau yang terakhir.
  
  while (current != null)
  {
    // Head -> 3 -> 5 -> 7 -> null
    // Head -> 3 ------> 7 -> null
    if (Current.Value.Equals(item))
    {
      // Ini adalah node yang tengah atau yang akhir.
      if (previous != null)
      {
        // Situasi 3b.
        previous.Next = current.Next;
        
        // Merupakan yang ujung, jadi perbarui _tail.
        if (current.Next == null)
        {
          _tail = previous;
        }
        else
        {
          // Sebelum: Head -> 3 <-> 5 <-> 7 -> null
          // Sesudah: Head -> 3 <-------> 7 -> null
          
          // previous = 3
          // current = 5
          // current.Next = 7
          // Jadi... 7.Previous = 3
          current.Next.Previous = previous;
        }
        
        Count--;
      }
      else
      {
        // Situasi 2 atau 3a.
        RemoveFirst();
      }
      
      return true;
    }
    
    previous = current;
    current = current.Next;
  }
  
  return false;
}

Tapi Kenapa?

Kita bisa menambahkan node ke awal dan akhir dari daftar-jadi? Pada posisinya sekaerang, class List yang tertaut ganda ini tidak lebih kuat daripada daftar tertaut tunggal. Tapi hanya dengan satu modifikasi kecil, kita bisa membuka semua perilaku yang memungkinkan. Dengan menjadikan property head dan tail property yang public dan read-only, pengguna daftar tertaut akan bisa menerapkan semua jenis perilaku yang baru.

public LinkedListNode Head
{
  get
  {
    return _head;
  }
}

public LinkedListNode Tail
{
  get
  {
    return _tail;
  }
}

Dengan perubahan sederhana ini kita bisa melakukan enumerasi secara manual terhadap daftar, yang memungkinkan kita untuk melakukan enumerasi dan pencarian terbalik (tail-to-head).

Misalnya, contoh kode berikut menunjukkan cara untuk menggunakan property Tail dan Previous dari daftar untuk mengenumerasi daftar itu secara terbalik dan melakukan pemrosesan pada tiap node.

public void ProcessListBackwards()
{
  LinkedList list = new LinkedList();
  PopulateList(list);
  
  LinkedListNode current = list.Tail;
  while (current != null)
  {
    ProcessNode(current);
    current = current.Previous;
  }
}

Sebagai tambahan, class List yang tertaut ganda juga memampukan kita untuk menciptakan class Deque, yang sendirinya merupakan dasar untuk membangun class lainnya. Kita akan mendiskusikan class ini nanti di bagian lain.

Selanjutnya

Ini menyelesaikan bagian kedua tentang daftar tertaut. Selanjutnya, kita akan membahas daftar array.