Struktur data dengan JavaScript: Singly-Linked List dan Doubly-Linked List

Dua dari yang paling umum diajarkan struktur data dalam ilmu komputer adalah singly-linked list dan doubly-linked list .

Ketika saya diajari struktur data ini, saya bertanya rekan-rekan saya untuk analogi konsep mereka. Apa yang saya dengar adalah beberapa contoh, seperti daftar belanjaan dan kereta api. Analogi ini, saat belajar akhirnya, itu tidak akurat. Daftar belanjaan adalah lebih analog antrian; kereta api adalah lebih analog kepada array.

Lebih banyak waktu berlalu, saya akhirnya menemukan sebuah analogi yang akurat digambarkan terkait singly-linked list dan doubly-linked list: Perburuan. Jika Anda ingin tahu tentang hubungan antara perburuan dan linked list, kemudian membaca di bawah ini untuk jawabannya!

Singly-Linked List

Dalam ilmu komputer, singly-linked list adalah struktur data yang memegang urutan node terhubung. Setiap node, pada gilirannya, berisi data dan pointer, yang dapat menunjukkan ke node lain.

Node singly-linked list mirip dengan langkah-langkah dalam perburuan. Setiap langkah berisi pesan (misalnya "Anda telah mencapai Prancis") dan lagnkah pointer ke berikutnya (misalnya "Kunjungi koordinat garis lintang dan bujur ini"). Ketika kita mulai sequencing langkah individu untuk membentuk urutan langkah, kami menciptakan perburuan.

Sekarang bahwa kita memiliki model konseptual dari singly-linked list, marilah kita mulai menjelajahi operasi singly-linked list.

Pengoperasian dari Singly-Linked List

Karena Singly-Linked List berisi node, yang dapat menjadii constructor yang terpisah dari Singly-Linked List, kami menggariskan operasi konstruktor kedua: Node dan SinglyList.

Node

• data menyimpan nilai.
• next poin ke node berikutnya dalam list.

SinglyList

• _length mengambil jumlah node dalam daftar.
• head menetapkan sebuah node sebagai kepala daftar.
• add(Value) menambahkan sebuah node ke daftar.
• searchNodeAt(position) mencari sebuah node pada n-posisi dalam daftar kami.
• remove(position) menghapus sebuah node dari daftar.

Pelaksanaan terkait Singly-Linked List

Untuk implementasi kami, kami akan pertama menentukan constructor yang bernama Node dan kemudian constructor yang bernama SinglyList.

Setiap instance Node memerlukan kemampuan untuk menyimpan data dan kemampuan untuk menunjuk ke node lain. Untuk menambahkan fungsi ini, kita akan menciptakan dua properti: data dan next.

1

function Node(data) {

2

    this.data = data;

3

    this.next = null;

4

}

Selanjutnya, kita perlu mendefinisikan SinglyList:

1

function SinglyList() {

2

    this._length = 0;

3

    this.head = null;

4

}

Setiap instance SinglyList akan memiliki dua properti: _length dan head. yang tadi ditetapkan jumlah node dalam daftar; poin terakhir untuk kepala daftar — node paling awal daftar. Karena setiap instance baru dari SinglyList tidak mengandung sebuah node, nilai default head null dan nilai default dari _length adalah 0.

Metode daftar Singly-Linked List

Kita perlu untuk menentukan metode yang dapat menambahkan, mencari, dan menghapus sebuah node dari daftar. Mari kita mulai dengan menambahkan node.

1 dari 3: add(value)

Mengagumkan, sekarang mari kita menerapkan fungsi untuk menambahkan node ke daftar.

1

SinglyList.prototype.add = function(value) {

2

    var node = new Node(value),

3

        currentNode = this.head;

4

5

    // 1st use-case: an empty list 

6

    if (!currentNode) {

7

        this.head = node;

8

        this._length++;

9

10

        return node;

11

    }

12

13

    // 2nd use-case: a non-empty list

14

    while (currentNode.next) {

15

        currentNode = currentNode.next;

16

    }

17

18

    currentNode.next = node;

19

20

    this._length++;

21

22

    return node;

23

};

Menambahkan node ke daftar kami melibatkan banyak langkah. Mari kita mulai dari awal metode. Kami menggunakan argumen add(value) untuk membuat sebuah instance baru dari sebuah Node, yang di assign ke variabel bernama node. Kami juga mendeklarasikan variabel bernama currentNode dan menginisialisasi untuk _head daftar kami. Jika tidak ada node dalam daftar, maka nilai head null.

Setelah titik ini dalam kode kita, kami menangani dua kasus penggunaan.

Kasus penggunaan pertama mempertimbangkan menambahkan node untuk sebuah daftar kosong. Jika head tidak menunjuk ke sebuah node, kemudian menetapkan node sebagai kepala daftar kami, kenaikan panjang daftar kami oleh satu, dan mengembalikan node.

Kasus penggunaan kedua mempertimbangkan menambahkan node ke daftar tidak kosong. Kita memasuki while loop, dan selama setiap iterasi, kita mengevaluasi jika currentNode.next menunjuk ke node lain. (Selama iterasi pertama, currentNode selalu menunjuk kepada kepala dari daftar.)

Jika jawabannya tidak, kami menetapkan node ke node currentNode.next dan mengembalikan node.

Jika jawabannya adalah ya, kita memasuki body while loop. Di dalam body, kita menetapkan kembali currentNode untuk currentNode.next. Ini proses diulang sampai currentNode.next tidak lagi menunjuk ke node lain. Dengan kata lain, currentNode poin ke node terakhir dari daftar kami.

while loop berhenti. Akhirnya, kami menetapkan node untuk currentNode.next, dan  menaikan _length oleh satu, dan kemudian kita mengembalikan node.

2 dari 3: searchNodeAt(position)

Kita sekarang bisa menambah node ke daftar kami, tapi kita tidak bisa mencari node pada posisi tertentu dalam daftar kami. Mari kita tambahkan fungsi ini dan menciptakan metode bernama searchNodeAt(position), yang menerima argumen bernama position. Argumen ini diharapkan menjadi integer yang menunjukkan sebuah node pada n-posisi dalam daftar kami.

1

SinglyList.prototype.searchNodeAt = function(position) {

2

    var currentNode = this.head,

3

        length = this._length,

4

        count = 1,

5

        message = {failure: 'Failure: non-existent node in this list.'};

6

7

    // 1st use-case: an invalid position 

8

    if (length === 0 || position < 1 || position > length) {

9

        throw new Error(message.failure);

10

    }

11

12

    // 2nd use-case: a valid position 

13

    while (count < position) {

14

        currentNode = currentNode.next;

15

        count++;

16

    }

17

18

    return currentNode;

19

};

Jika pernyataan if memeriksa kasus penggunaan pertama: posisi tidak valid dilewatkan sebagai argumen.

Jika index yang dimasukan ke searchNodeAt(position) valid, maka kita mencapai kasus penggunaan kedua — while loop. Selama setiap pengulangan while loop, currentNode — yang menunjuk ke head — dipindahkan ke node berikutnya dalam daftar. Pengulangan ini berlanjut sampai jumlah sama dengan posisi.

Ketika loop akhirnya berhenti, currentNode dikembalikan.

3 dari 3: remove(position)

Metode terakhir kita buat dinamai remove(position).

1

SinglyList.prototype.remove = function(position) {

2

    var currentNode = this.head,

3

        length = this._length,

4

        count = 0,

5

        message = {failure: 'Failure: non-existent node in this list.'},

6

        beforeNodeToDelete = null,

7

        nodeToDelete = null,

8

        deletedNode = null;

9

10

    // 1st use-case: an invalid position

11

    if (position < 0 || position > length) {

12

        throw new Error(message.failure);

13

    }

14

15

    // 2nd use-case: the first node is removed

16

    if (position === 1) {

17

        this.head = currentNode.next;

18

        deletedNode = currentNode;

19

        currentNode = null;

20

        this._length--;

21

22

        return deletedNode;

23

    }

24

25

    // 3rd use-case: any other node is removed

26

    while (count < position) {

27

        beforeNodeToDelete = currentNode;

28

        nodeToDelete = currentNode.next;

29

        count++;

30

    }

31

32

    beforeNodeToDelete.next = nodeToDelete.next;

33

    deletedNode = nodeToDelete;

34

    nodeToDelete = null;

35

    this._length--;

36

37

    return deletedNode;

38

};

Pelaksanaan remove(position) kami melibatkan menggunakan tiga kasus:

1. Posisi tidak valid dimasukan sebagai argumen.
2. Posisi satu (head dari daftar) dimasukan sebagai argumen.
3. Posisi yang ada (bukan posisi pertama) dimasukan sebagai argumen.

Penggunaan pertama dan kasus kedua yang paling sederhana untuk ditangani. Dalam hal skenario pertama, jika daftar kosong atau posisi ketidakwujudan dimasukan, error dilemparkan.

Kasus penggunaan kedua menangani penghapusan node yang pertama dalam daftar, yang juga head. Jika hal ini terjadi, maka logika berikut terjadi:

1. head dipindahkan ke currentNode.next.
2. deletedNode poin ke currentNode.
3. currentNode dipindahkan ke null.
4. Mengurangi _length daftar kami oleh satu.
5. deletedNode di kembalikan.

Skenario yang ketiga adalah yang paling sulit untuk dimengerti. Kompleksitas berasal dari kebutuhan pelacakan dua node selama setiap pengulangan while loop. Selama setiap iterasi loop kami, kami melacak node sebelum node dihapus dan node dihapus. Ketika loop kami akhirnya mencapai node pada posisi kami ingin hapus, loop berakhir.

Pada titik ini, kami memegang referensi ke tiga simpul: beforeNodeToDelete, nodeToDelete, dan deletedNode. Sebelum menghapus nodeToDelete, kita harus assign nilai dari next nilainya dari di depan nilai beforeNodeToDelete. Jika tujuan dari langkah ini tampak jelas, mengingatkan diri sendiri bahwa kita memiliki daftar terkait node; hanya mengeluarkan sebuah node yang berhenti di link dari node pertama dari daftar ke node terakhir dari daftar.

Selanjutnya, kami menetapkan deletedNode ke nodeToDelete. Kemudian kita menetapkan nilai nodeToDelete ke null, pengurangan panjang daftar oleh satu dan mengembalikan deletedNode.

Implementasi lengkap daftar Singly-Linked List

Pelaksanaan lengkap daftar adalah di sini:

1

function Node(data) {

2

    this.data = data;

3

    this.next = null;

4

}

5

6

function SinglyList() {

7

    this._length = 0;

8

    this.head = null;

9

}

10

11

SinglyList.prototype.add = function(value) {

12

    var node = new Node(value),

13

        currentNode = this.head;

14

15

    // 1st use-case: an empty list

16

    if (!currentNode) {

17

        this.head = node;

18

        this._length++;

19

20

        return node;

21

    }

22

23

    // 2nd use-case: a non-empty list

24

    while (currentNode.next) {

25

        currentNode = currentNode.next;

26

    }

27

28

    currentNode.next = node;

29

30

    this._length++;

31

32

    return node;

33

};

34

35

SinglyList.prototype.searchNodeAt = function(position) {

36

    var currentNode = this.head,

37

        length = this._length,

38

        count = 1,

39

        message = {failure: 'Failure: non-existent node in this list.'};

40

41

    // 1st use-case: an invalid position

42

    if (length === 0 || position < 1 || position > length) {

43

        throw new Error(message.failure);

44

    }

45

46

    // 2nd use-case: a valid position

47

    while (count < position) {

48

        currentNode = currentNode.next;

49

        count++;

50

    }

51

52

    return currentNode;

53

};

54

55

SinglyList.prototype.remove = function(position) {

56

    var currentNode = this.head,

57

        length = this._length,

58

        count = 0,

59

        message = {failure: 'Failure: non-existent node in this list.'},

60

        beforeNodeToDelete = null,

61

        nodeToDelete = null,

62

        deletedNode = null;

63

64

    // 1st use-case: an invalid position

65

    if (position < 0 || position > length) {

66

        throw new Error(message.failure);

67

    }

68

69

    // 2nd use-case: the first node is removed

70

    if (position === 1) {

71

        this.head = currentNode.next;

72

        deletedNode = currentNode;

73

        currentNode = null;

74

        this._length--;

75

76

        return deletedNode;

77

    }

78

79

    // 3rd use-case: any other node is removed

80

    while (count < position) {

81

        beforeNodeToDelete = currentNode;

82

        nodeToDelete = currentNode.next;

83

        count++;

84

    }

85

86

    beforeNodeToDelete.next = nodeToDelete.next;

87

    deletedNode = nodeToDelete;

88

    nodeToDelete = null;

89

    this._length--;

90

91

    return deletedNode;

92

};

Dari Singly ke Doubly

Mengagumkan, implementasi terkait singly-linked list lengkap. Kita sekarang dapat menggunakan struktur data yang menambah, menghapus, dan mencari node dalam daftar yang menempati ruang yang non-berdekatan dalam memori.

Namun, saat ini, semua operasi kami mulai dari awal daftar dan lari ke akhir daftar. Dengan kata lain, mereka uni-directional.

Mungkin ada kasus di mana kita ingin operasi kami menjadi bi-directional. Jika Anda mempertimbangkan kasus penggunaan ini, maka Anda hanya menggambarkan doubly-linked list.

Doubly-Linked List

doubly-linked list semua fungsi dari singly-linked list  dan menambah untuk bi-directional gerakan dalam daftar. Kita dapat melintasi, dengan kata lain, linked list dari node pertama dalam daftar ke node terakhir pada daftar; dan kita dapat melintasi dari node terakhir dalam daftar ke node yang pertama dalam daftar.

Dalam bagian ini, kita akan menjaga fokus kami terutama pada perbedaan antara doubly-linked list  dan singly-linked list..

Operasi dari Doubly-Linked List

Daftar kami akan mencakup dua konstruktor: Node dan DoublyList. Mari kita menguraikan operasi mereka.

Node

• data menyimpan nilai.
• next berikutnya ke node berikutnya dalam daftar.
• previous poin-poin ke node sebelumnya dalam daftar.

DoublyList

• _length mengambil jumlah node dalam daftar.
• head menetapkan sebuah node sebagai kepala dari daftar.
• tail menetapkan sebuah node sebagai ekor dari daftar.
• add(value) menambahkan sebuah node ke daftar.
• searchNodeAt(position) mencari sebuah node pada n-posisi dalam daftar kami.
• remove(position) menghapus sebuah node dari daftar.

Implementasi dari Doubly-Linked List

Ayo menulis beberapa kode!

Untuk pelaksanaan kami, kami akan membuat constructor yang bernama Node:

1

function Node(value) {

2

    this.data = value;

3

    this.previous = null;

4

    this.next = null;

5

}

Untuk membuat gerakan bi-directional dari doubly-linked list,, kita perlu properti titik di kedua arah dari daftar. Properti ini telah bernama previous dan next.

Selanjutnya, kita perlu untuk mengimplementasikan DoublyList dan menambahkan tiga properti: _length, head dan tail. Tidak seperti singly-linked list, doubly-linked list memiliki referensi ke awal daftar dan akhir daftar. Karena setiap instance DoublyList diinisialisasi tanpa node, nilai-nilai default dari head dan tail ditetapkan ke null.

1

function DoublyList() {

2

    this._length = 0;

3

    this.head = null;

4

    this.tail = null;

5

}

Metode dari Doubly-Linked List

Kita sekarang akan mengeksplorasi metode berikut: add(value), remove(position) dan searchNodeAt(position). Semua metode ini digunakan untuk singly-linked list;; Namun, mereka harus disusun ulang untuk gerakan bi-directional.

1 dari 3: add(value)

1

DoublyList.prototype.add = function(value) {

2

    var node = new Node(value);

3

4

    if (this._length) {

5

        this.tail.next = node;

6

        node.previous = this.tail;

7

        this.tail = node;

8

    } else {

9

        this.head = node;

10

        this.tail = node;

11

    }

12

13

    this._length++;

14

15

    return node;

16

};

Dalam metode ini, kita memiliki dua skenario. Pertama, jika daftar kosong, kemudian menetapkan ke head dan tail node ditambahkan. Kedua, jika daftar berisi node, kemudian menemukan ekor daftar dan menetapkan ke tail.next node yang ditambahkan; demikian juga, kita perlu mengkonfigurasi ekor baru untuk gerakan bi-directional. Kita perlu untuk mengatur, dengan kata lain, tail.previous di ekor asli.

2 dari 3: searchNodeAt(position)

Implementasi searchNodeAt(position) identik dengan singly-linked list. Jika Anda lupa bagaimana untuk menerapkannya, saya mencantumkan itu di bawah ini:

1

DoublyList.prototype.searchNodeAt = function(position) {

2

    var currentNode = this.head,

3

        length = this._length,

4

        count = 1,

5

        message = {failure: 'Failure: non-existent node in this list.'};

6

7

    // 1st use-case: an invalid position 

8

    if (length === 0 || position < 1 || position > length) {

9

        throw new Error(message.failure);

10

    }

11

12

    // 2nd use-case: a valid position 

13

    while (count < position) {

14

        currentNode = currentNode.next;

15

        count++;

16

    }

17

18

    return currentNode;

19

};

3 dari 3: remove(position)

Metode ini akan menjadi yang paling menantang untuk dipahami. Aku akan menampilkan kode dan kemudian menjelaskannya.

1

DoublyList.prototype.remove = function(position) {

2

    var currentNode = this.head,

3

        length = this._length,

4

        count = 1,

5

        message = {failure: 'Failure: non-existent node in this list.'},

6

        beforeNodeToDelete = null,

7

        nodeToDelete = null,

8

        deletedNode = null;

9

10

    // 1st use-case: an invalid position

11

    if (length === 0 || position < 1 || position > length) {

12

        throw new Error(message.failure);

13

    }

14

15

    // 2nd use-case: the first node is removed

16

    if (position === 1) {

17

        this.head = currentNode.next;

18

19

        // 2nd use-case: there is a second node

20

        if (!this.head) {

21

            this.head.previous = null;

22

        // 2nd use-case: there is no second node

23

        } else {

24

            this.tail = null;

25

        }

26

27

    // 3rd use-case: the last node is removed

28

    } else if (position === this._length) {

29

        this.tail = this.tail.previous;

30

        this.tail.next = null;

31

    // 4th use-case: a middle node is removed

32

    } else {

33

        while (count < position) {

34

            currentNode = currentNode.next;

35

            count++;

36

        }

37

38

        beforeNodeToDelete = currentNode.previous;

39

        nodeToDelete = currentNode;

40

        afterNodeToDelete = currentNode.next;

41

42

        beforeNodeToDelete.next = afterNodeToDelete;

43

        afterNodeToDelete.previous = beforeNodeToDelete;

44

        deletedNode = nodeToDelete;

45

        nodeToDelete = null;

46

    }

47

48

    this._length--;

49

50

    return message.success;

51

};

remove(position) menangani empat use case:

1. Posisi yang dimasukan sebagai argumen dari remove(position) tidak ada. Dalam kasus ini, kita melempar kesalahan.
2. Posisi yang dimasukan sebagai argumen dari remove(position) adalah node pertama (head) dari daftar. Jika hal ini terjadi, kami akan menetapkan deletedNode ke head dan kemudian menetapkan kembali head ke node berikutnya dalam daftar. Saat ini, kita harus mempertimbangkan jika daftar kami memiliki lebih dari satu node. Jika jawabannya tidak, head akan ditetapkan ke null dan kita akan masuk if bagian dari pernyataan if-else . Dalam tubuh if, kita juga harus menetapkan tail ke null — dengan kata lain, kita mengembalikan ke keadaan semula dari sebuah daftar kosong doubly-linked list. Jika kami menghapus node pertama dalam daftar dan kami memiliki lebih dari satu node dalam daftar kami, kita memasuki bagian else dari pernyataan if-else. Dalam kasus ini, kita harus benar menetapkan properti previous head ke null — tidak ada node sebelum kepala dari daftar.
3. Posisi yang dimasukan sebagai argumen dari remove(position) adalah ekor dari daftar. Pertama, deletedNode diassign me tail. Kedua, tail dipindahkan ke node sebelum ekor. Ketiga, ekor baru memiliki node tidak setelah itu dan membutuhkan nilai next harus ditetapkan ke null.
4. Banyak yang terjadi di sini, jadi saya akan memfokuskan pada logika daripada setiap baris kode. Kita berhentikan while loop begitu currentNode menunjuk ke node pada posisi yang dimasukan sebagai argumen untuk remove(position). Saat ini, kami menetapkan kembali nilai beforeNodeToDelete.next ke node setelah nodeToDelete dan, sebaliknya, kami menetapkan kembali nilai afterNodeToDelete.previous ke node sebelum nodeToDelete. Dengan kata lain, kami menghapus pointer ke node yang dihapus dan menetapkan kembali mereka ke node yang benar. Selanjutnya, kami menetapkan deletedNode ke nodeToDelete. Akhirnya, kami menetapkan nodeToDelete ke null.

Akhirnya, kami mengurangi panjang daftar dan mengembalikan deletedNode kami.

Implementasi lengkap Doubly-Linked List

Berikut adalah seluruh implementasinya:

1

function Node(value) {

2

    this.data = value;

3

    this.previous = null;

4

    this.next = null;

5

}

6

7

function DoublyList() {

8

    this._length = 0;

9

    this.head = null;

10

    this.tail = null;

11

}

12

13

DoublyList.prototype.add = function(value) {

14

    var node = new Node(value);

15

16

    if (this._length) {

17

        this.tail.next = node;

18

        node.previous = this.tail;

19

        this.tail = node;

20

    } else {

21

        this.head = node;

22

        this.tail = node;

23

    }

24

25

    this._length++;

26

27

    return node;

28

};

29

30

DoublyList.prototype.searchNodeAt = function(position) {

31

    var currentNode = this.head,

32

        length = this._length,

33

        count = 1,

34

        message = {failure: 'Failure: non-existent node in this list.'};

35

36

    // 1st use-case: an invalid position

37

    if (length === 0 || position < 1 || position > length) {

38

        throw new Error(message.failure);

39

    }

40

41

    // 2nd use-case: a valid position

42

    while (count < position) {

43

        currentNode = currentNode.next;

44

        count++;

45

    }

46

47

    return currentNode;

48

};

49

50

DoublyList.prototype.remove = function(position) {

51

    var currentNode = this.head,

52

        length = this._length,

53

        count = 1,

54

        message = {failure: 'Failure: non-existent node in this list.'},

55

        beforeNodeToDelete = null,

56

        nodeToDelete = null,

57

        deletedNode = null;

58

59

    // 1st use-case: an invalid position

60

    if (length === 0 || position < 1 || position > length) {

61

        throw new Error(message.failure);

62

    }

63

64

    // 2nd use-case: the first node is removed

65

    if (position === 1) {

66

        this.head = currentNode.next;

67

68

        // 2nd use-case: there is a second node

69

        if (!this.head) {

70

            this.head.previous = null;

71

        // 2nd use-case: there is no second node

72

        } else {

73

            this.tail = null;

74

        }

75

76

    // 3rd use-case: the last node is removed

77

    } else if (position === this._length) {

78

        this.tail = this.tail.previous;

79

        this.tail.next = null;

80

    // 4th use-case: a middle node is removed

81

    } else {

82

        while (count < position) {

83

            currentNode = currentNode.next;

84

            count++;

85

        }

86

87

        beforeNodeToDelete = currentNode.previous;

88

        nodeToDelete = currentNode;

89

        afterNodeToDelete = currentNode.next;

90

91

        beforeNodeToDelete.next = afterNodeToDelete;

92

        afterNodeToDelete.previous = beforeNodeToDelete;

93

        deletedNode = nodeToDelete;

94

        nodeToDelete = null;

95

    }

96

97

    this._length--;

98

99

    return message.success;

100

};

Kesimpulan

Kita telah membahas banyak informasi dalam artikel ini. Jika semua itu menjadi membingungkan, baca lagi, dan bereksperimen dengan kode. Ketika akhirnya masuk akal bagi Anda, merasalah bangga. Anda hanya telah mengungkapkan misteri singly-linked list dan doubly-linked list. Anda dapat menambahkan struktur data ini untuk pengkodean sabuk-alat Anda!