JavaScript中链表的详细介绍
本篇文章给大家带来的内容是关于JavaScript中链表的详细介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
链表和数组
大家都用过js中的数组,数组其实是一种线性表的顺序存储结构,它的特点是用一组地址连续的存储单元依次存储数据元素。而它的缺点也正是其特点而造成,比如对数组做删除或者插入的时候,可能需要移动大量的元素。
这里大致模拟一下数组的插入操作:
insert(arr, index, data){ for(let i = index + 1; i < arr.length; i++){ arr[i] = arr[i - 1]; } arr[index] = data; }
从上面的代码可以看出数组的插入以及删除都有可能会是一个O(n)的操作。从而就引出了链表这种数据结构,链表不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的缺点,当然它也失去了数组在一块连续空间内随机存取的优点。
单向链表
单向链表的特点:
用一组任意的内存空间去存储数据元素(这里的内存空间可以是连续的,也可以是不连续的)
每个节点(node)都由数据本身和一个指向后续节点的指针组成
整个链表的存取必须从头指针开始,头指针指向第一个节点
最后一个节点的指针指向空(NULL)
链表中的几个主要操作
创建节点
插入节点
搜索/遍历节点
删除节点
合并
初始化节点
指针指向空
存储数据
class Node { constructor(key) { this.next = null; this.key = key; } }
初始化单向链表
每个链表都有一个头指针,指向第一个节点,没节点则指向NULL
class List { constructor() { this.head = null; } }
创建节点
static createNode(key) { return new createNode(key); }
这里说明一下,这一块我是向外暴露了一个静态方法来创建节点,而并非直接把它封装进插入操作里去,因为我感觉这样的逻辑会更加正确一些。 从创建一个链表 -> 创建一个节点 -> 将节点插入进链表中。可能你会遇到一些文章介绍的方式是直接将一个数据作为参数去调用insert操作,在insert内部做了一个创建节点。
插入节点(插入到头节点之后)
插入操作只需要去调整节点的指针即可,两种情况:
head没有指向任何节点,说明当前插入的节点是第一个
head指向新节点
新节点的指针指向NULL
head有指向的节点
head指向新的节点
新节点的指针指向原本head所指向的节点
insert(node) { // 如果head有指向的节点 if(this.head){ node.next = this.head; }else { node.next = null; } this.head = node; }
搜索节点
从head开始查找
找到节点中的key等于想要查找的key的时候,返回该节点
find(key) { let node = this.head; while(node !== null && node.key !== key){ node = node.next; } return node; }
删除节点
这里分三种情况:
所要删除的节点刚好是第一个,也就是head指向的节点
将head指向所要删除节点的下一个节点(node.next)
要删除的节点为最后一个节点
寻找到所要删除节点的上一个节点(prevNode)
将prevNode中的指针指向NULL
在列表中间删除某个节点
寻找到所要删除节点的上一个节点(prevNode)
将prevNode中的指针指向当前要删除的这个节点的下一个节点
delete(node) { // 第一种情况 if(node === this.head){ this.head = node.next; return; } // 查找所要删除节点的上一个节点 let prevNode = this.head; while (prevNode.next !== node) { prevNode = prevNode.next; } // 第二种情况 if(node.next === null) { prevNode.next = null; } // 第三种情况 if(node.next) { prevNode.next = node.next; } }
单向链表整体的代码
class ListNode { constructor(key) { this.next = null; this.key = key; } } class List { constructor() { this.head = null; this.length = 0; } static createNode(key) { return new ListNode(key); } // 往头部插入数据 insert(node) { // 如果head后面有指向的节点 if (this.head) { node.next = this.head; } else { node.next = null; } this.head = node; this.length++; } find(key) { let node = this.head; while (node !== null && node.key !== key) { node = node.next; } return node; } delete(node) { if (this.length === 0) { throw 'node is undefined'; } if (node === this.head) { this.head = node.next; this.length--; return; } let prevNode = this.head; while (prevNode.next !== node) { prevNode = prevNode.next; } if (node.next === null) { prevNode.next = null; } if (node.next) { prevNode.next = node.next; } this.length--; } }
双向链表
如果你把上面介绍的单向列表都看明白了,那么这里介绍的双向列表其实差不多。
从上面的图可以很清楚的看到双向链表和单向链表的区别。双向链表多了一个指向上一个节点的指针。
初始化节点
指向前一个节点的指针
指向后一个节点的指针
节点数据
class ListNode { this.prev = null; this.next = null; this.key = key; }
初始化双向链表
头指针指向NULL
class List { constructor(){ this.head = null; } }
创建节点
static createNode(key){ return new ListNode(key); }
插入节点((插入到头节点之后)
看上图中head后面的第一个节点可以知道,该节点的prev指向NULL
节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点
如果head后有节点,那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)
最后将head指向新的节点
insert(node) { node.prev = null; node.next = this.head; if(this.head){ this.head.prev = node; } this.head = node; }
搜索节点
这里和单向节点一样,就直接贴代码了
search(key) { let node = this.head; while (node !== null && node.key !== key) { node = node.next; } return node; }
删除节点
和之前单向链表一样,分三种情况去看:
删除的是第一个节点
head指向所要删除节点的下一个节点
下一个节点的prev指针指向所要删除节点的上一个节点
删除的是中间的某个节点
所要删除的前一个节点的next指向所要删除的下一个节点
所要删除的下一个节点的prev指向所要删除的前一个节点
删除的是最后一个节点
要删除的节点的上一个节点的next指向null(也就是指向删除节点的next所指的地址)
delete(node) { const {prev,next} = node; delete node.prev; delete node.next; if(node === this.head){ this.head = next; } if(next){ next.prev = prev; } if(prev){ prev.next = next; } }
双向链表整体代码
class ListNode { constructor(key) { // 指向前一个节点 this.prev = null; // 指向后一个节点 this.next = null; // 节点的数据(或者用于查找的键) this.key = key; } } /** * 双向链表 */ class List { constructor() { this.head = null; } static createNode(key) { return new ListNode(key); } insert(node) { node.prev = null; node.next = this.head; if (this.head) { this.head.prev = node; } this.head = node; } search(key) { let node = this.head; while (node !== null && node.key !== key) { node = node.next; } return node; } delete(node) { const { prev, next } = node; delete node.prev; delete node.next; if (node === this.head) { this.head = next; } if (prev) { prev.next = next; } if (next) { next.prev = prev; } } }
总结
这里做一个小总结吧,可能有一部分人读到这里还不是特别的明白,我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念,就是有一个head,然后在有好多的节点(Node),然后用一个指针把他们串起来就好了,至于里面的插入操作也好,删除也好,其实都是在调整节点中指针的指向。
Atas ialah kandungan terperinci JavaScript中链表的详细介绍. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Apabila menggunakan struktur data kompleks dalam Java, Comparator digunakan untuk menyediakan mekanisme perbandingan yang fleksibel. Langkah-langkah khusus termasuk: mentakrifkan kelas pembanding, menulis semula kaedah bandingkan untuk menentukan logik perbandingan. Buat contoh pembanding. Gunakan kaedah Collections.sort, menghantar contoh koleksi dan pembanding.

Jenis rujukan ialah jenis data khas dalam bahasa Go Nilai mereka tidak menyimpan data itu sendiri secara langsung, tetapi alamat data yang disimpan. Dalam bahasa Go, jenis rujukan termasuk kepingan, peta, saluran dan penunjuk. Pemahaman mendalam tentang jenis rujukan adalah penting untuk memahami pengurusan memori dan kaedah pemindahan data bahasa Go. Artikel ini akan menggabungkan contoh kod khusus untuk memperkenalkan ciri dan penggunaan jenis rujukan dalam bahasa Go. 1. Slices Slices ialah salah satu jenis rujukan yang paling biasa digunakan dalam bahasa Go.

Struktur data dan algoritma ialah asas pembangunan Java Artikel ini meneroka secara mendalam struktur data utama (seperti tatasusunan, senarai terpaut, pepohon, dll.) dan algoritma (seperti pengisihan, carian, algoritma graf, dll.) dalam Java. Struktur ini diilustrasikan dengan contoh praktikal, termasuk menggunakan tatasusunan untuk menyimpan skor, senarai terpaut untuk mengurus senarai beli-belah, tindanan untuk melaksanakan rekursi, baris gilir untuk menyegerakkan benang, dan pepohon dan jadual cincang untuk carian dan pengesahan pantas. Memahami konsep ini membolehkan anda menulis kod Java yang cekap dan boleh diselenggara.

Pengenalan kepada JS-Torch JS-Torch ialah perpustakaan JavaScript pembelajaran mendalam yang sintaksnya hampir sama dengan PyTorch. Ia mengandungi objek tensor berfungsi sepenuhnya (boleh digunakan dengan kecerunan yang dijejaki), lapisan dan fungsi pembelajaran mendalam, dan enjin pembezaan automatik. JS-Torch sesuai untuk penyelidikan pembelajaran mendalam dalam JavaScript dan menyediakan banyak alatan dan fungsi yang mudah untuk mempercepatkan pembangunan pembelajaran mendalam. Image PyTorch ialah rangka kerja pembelajaran mendalam sumber terbuka yang dibangunkan dan diselenggara oleh pasukan penyelidik Meta. Ia menyediakan set alat dan perpustakaan yang kaya untuk membina dan melatih model rangkaian saraf. PyTorch direka bentuk untuk menjadi ringkas, fleksibel dan mudah digunakan, dan ciri graf pengiraan dinamiknya menjadikan

Gambaran Keseluruhan Rangka Kerja Koleksi Java Rangka kerja pengumpulan Java ialah bahagian penting dalam bahasa pengaturcaraan Java Ia menyediakan satu siri perpustakaan kelas kontena yang boleh menyimpan dan mengurus data. Pustaka kelas kontena ini mempunyai struktur data yang berbeza untuk memenuhi keperluan penyimpanan dan pemprosesan data dalam senario yang berbeza. Kelebihan rangka kerja koleksi ialah ia menyediakan antara muka bersatu, membolehkan pembangun mengendalikan perpustakaan kelas kontena yang berbeza dengan cara yang sama, dengan itu mengurangkan kesukaran pembangunan. Struktur data rangka kerja pengumpulan Java Rangka kerja pengumpulan Java mengandungi pelbagai struktur data, setiap satunya mempunyai ciri unik dan senario yang boleh digunakan. Berikut adalah beberapa struktur data rangka kerja pengumpulan Java yang biasa: 1. Senarai: Senarai ialah koleksi tersusun yang membolehkan elemen diulang. Li

Pokok AVL ialah pokok carian binari seimbang yang memastikan operasi data yang pantas dan cekap. Untuk mencapai keseimbangan, ia melakukan operasi belok kiri dan kanan, melaraskan subpokok yang melanggar keseimbangan. Pokok AVL menggunakan pengimbangan ketinggian untuk memastikan ketinggian pokok sentiasa kecil berbanding bilangan nod, dengan itu mencapai kerumitan masa logaritma (O(logn)) operasi carian dan mengekalkan kecekapan struktur data walaupun pada set data yang besar.

Go dan Node.js mempunyai perbezaan dalam menaip (kuat/lemah), konkurensi (goroutine/gelung peristiwa) dan pengumpulan sampah (automatik/manual). Go mempunyai daya pemprosesan yang tinggi dan kependaman rendah, dan sesuai untuk bahagian belakang beban tinggi Node.js bagus pada I/O tak segerak dan sesuai untuk permintaan serentak tinggi dan pendek. Kes praktikal kedua-duanya termasuk Kubernetes (Go), sambungan pangkalan data (Node.js) dan aplikasi web (Go/Node.js). Pilihan terakhir bergantung pada keperluan aplikasi, kemahiran pasukan, dan keutamaan peribadi.

Kajian mendalam tentang misteri struktur data bahasa Go memerlukan contoh kod khusus Sebagai bahasa pengaturcaraan yang ringkas dan cekap, bahasa Go juga menunjukkan daya tarikannya yang unik dalam memproses struktur data. Struktur data adalah konsep asas dalam sains komputer, yang bertujuan untuk mengatur dan mengurus data supaya ia boleh diakses dan dimanipulasi dengan lebih cekap. Dengan mempelajari secara mendalam tentang misteri struktur data bahasa Go, kami dapat memahami dengan lebih baik cara data disimpan dan dikendalikan, seterusnya meningkatkan kecekapan pengaturcaraan dan kualiti kod. 1. Array Array ialah salah satu struktur data yang paling mudah
