この記事では、JavaScript の単一リンク リストと循環リンク リストのデータ構造を主に紹介し、JavaScript が単一リンク リストと循環リンク リストを実装する方法について詳しく紹介します。興味のある方は学習してください
データ構造シリーズの序章。 :
データ構造として プログラマの基礎知識は、私たち一人ひとりがしっかりと理解しておく必要があります。最近は、当時掘った穴を補うために、データ構造の二度目の勉強も始めています。 。 。 。 。 。授業中は講義に従うだけで、自分でデータ構造を実装することはなく、ましてやデータ構造を使用して問題を解決することはありませんでした。今は穴を埋めて奮闘するときです。私のブログを読んでいる子供たちに、もしあなたがまだ学校に通っているなら、この時点で掘られた穴を埋める必要があるので、基礎コースの学習を決して過小評価しないでください。 2倍の努力をすれば、それは人の能力などに直接影響します。 。 。 。 。 。 自分で穴を掘らないでください
リンク リストのデータ構造の知識について、ここで簡単に説明します:
リンク リストは、物理ストレージにおける非線形かつ非連続のデータ構造です。ユニット (論理的には線形) であり、その各ノードはデータ フィールドとポインター フィールドの 2 つのフィールドで構成されます。実際のデータはデータ フィールドに格納され、ポインタ フィールドにはリンク リスト内の次の要素または前の要素を指すポインタ情報が格納されます。ポインタが存在するからこそ、連結リストの格納は物理単位で不連続となる。
リンクリストの長所と短所も同様に明らかです。線形リストと比較すると、リンク リストは、要素の移動が必要な線形リスト (配列) とは異なり、ポインタ情報を変更するだけで操作を完了できるため、ノードの追加と削除がより効率的です。同様に、リンクされたリストの長さは理論的には無限で (メモリ容量の範囲内で)、長さは動的に変更できるため、線形リストに比べて大きな利点があります。 同様に、線形テーブルはノードにランダムにアクセスできず、リンク リストに沿ったポインター トラバーサル クエリを通じてのみアクセスできるため、データ要素へのアクセス効率は比較的低くなります。
以下は、JS 部分にカプセル化された一般的なメソッドと説明です
:
| Method | Description |
|---|---|
| append(element) | リンクされたリストの最後にノード要素を追加します |
| insert(position,element) | 位置positionにノード要素を挿入 |
| removeAt(position) | インデックス値に応じてノードを削除position |
| remove(element) | 指定されたノードを検索して削除しますelement |
| remove() | リンクリストの最後のノードを削除 |
| indexOf(element) | 指定されたノード要素のインデックス値を見つけて返す |
| isEmpty() | かどうかを判断するリンクされたリストは空です |
| size() | リンクされたリストの長さを取得します |
| toString() | 文字列出力に変換します |
| getHead() | ヘッドノードを取得します |
| getTail() | 尾ノードを取得する |
一般的に使用されるさまざまなメソッドのアルゴリズムの説明は、結局のところ、非常に基本的な知識なので、誰でも簡単に読んで理解できると思います。
単一リンクリスト:
function LinkedList(){
/*节点定义*/
var Node = function(element){
this.element = element; //存放节点内容
this.next = null; //指针
}
var length = 0, //存放链表长度
head = null; //头指针
this.append = function(element){
var node = new Node(element),
current; //操作所用指针
if (!head){
head = node;
}else {
current = head;
while(current.next){
current = current.next;
}
current.next = node;
}
length++;
return true;
};
this.insert = function(position, element){
if (position >= 0 && position <= length) {
var node = new Node(element),
current = head,
previous,
index = 0;
if(position === 0){
node.next = current;
head = node;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
previous,
index = 0;
if (position === 0) {
head = current.next;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
};
length--;
return current.element;
}else{
return null;
}
};
this.remove = function(element){
var current = head,
previous;
if(element === current.element){
head = current.next;
length--;
return true;
}
previous = current;
current = current.next;
while(current){
if(element === current.element){
previous.next = current.next;
length--;
return true;
}else{
previous = current;
current = current.next;
}
}
return false;
};
this.remove = function(){
if(length < 1){
return false;
}
var current = head,
previous;
if(length == 1){
head = null;
length--;
return current.element;
}
while(current.next !== null){
previous = current;
current = current.next;
}
previous.next = null;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current){
if(element === current.element){
return index;
}
index++;
current = current.next;
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '';
while(current){
string += current.element;
current = current.next;
}
return string;
};
this.getHead = function(){
return head;
}
}循環リンクリスト: 単一リンクリストに基づいて、末尾ノードのポインタを先頭ノードに向けて循環リンクリストを形成します。循環リンク リスト内の任意のノードから開始して、リンク リスト全体をたどることができます。
function CircularLinkedList(){
var Node = function(element){
this.element = element;
this.next = null;
}
var length = 0,
head = null;
this.append = function(element){
var node = new Node(element),
current;
if (!head) {
head = node;
node.next = head;
}else{
current = head;
while(current.next !== head){
current = current.next;
}
current.next = node;
node.next = head;
};
length++;
return true;
};
this.insert = function(position, element){
if(position > -1 && position < length){
var node = new Node(element),
index = 0,
current = head,
previous;
if (position === 0) {
node.next = head;
head = node;
}else{
while(index++ < position){
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
};
length++;
return true;
}else{
return false;
}
};
this.removeAt = function(position){
if(position > -1 && position < length){
var current = head,
previous,
index = 0;
if (position === 0) {
head = current.next;
}else{
while (index++ < position){
previous = current;
current = current.next;
}
previous.next = current.next;
};
length--;
return current.element;
}else{
return null;
}
};
this.remove = function (element){
var current = head,
previous,
indexCheck = 0;
while(current && indexCheck < length){
if(current.element === element){
if(indexCheck == 0){
head = current.next;
length--;
return true;
}else{
previous.next = current.next;
length--;
return true;
}
}else{
previous = current;
current = current.next;
indexCheck++;
}
}
return false;
};
this.remove = function(){
if(length === 0){
return false;
}
var current = head,
previous,
indexCheck = 0;
if(length === 1){
head = null;
length--;
return current.element;
}
while(indexCheck++ < length){
previous = current;
current = current.next;
}
previous.next = head;
length--;
return current.element;
};
this.indexOf = function(element){
var current = head,
index = 0;
while(current && index < length){
if(current.element === element){
return index;
}else{
index++;
current = current.next;
}
}
return false;
};
this.isEmpty = function(){
return length === 0;
};
this.size = function(){
return length;
};
this.toString = function(){
var current = head,
string = '',
indexCheck = 0;
while(current && indexCheck < length){
string += current.element;
current = current.next;
indexCheck++;
}
return string;
};
}使い方:
クラス外での拡張メソッド:
以上、皆さんの参考になれば幸いです。
関連記事:
nodejsでの最大コールスタックエラーの超過を解決する方法
Vue+SpringBootでブログ管理プラットフォームを実装する方法
以上がJavaScript で単一リンク リストと循環リンク リストを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
