単独連結リスト
4668 ワード
何がシングルリンクスリストですか?
シングルリンクリストは、ノードのコレクションであり、各ノードは、別のノードまたはnullへのポインタと値を持っています.値は有効なデータ型を指定できます.下記の図に示すようになります.
リンクリストのエントリノードはheadと呼ばれ、最後のノードはtailと呼ばれます.
JavaScriptでは、このようにリンクリストを実装することができます
リストの利点 挿入と削除は簡単に行うことができます 配列とは異なり、挿入と削除の要素の動きは必要ありません.
シングルリンク一覧 検索操作はリンクリストで遅いです.配列と異なり、データ要素のランダムアクセスは許可されません.ノードは最初のノードから順にアクセスされます.
ビッグO表記 アクセスo ( n ) 探索o ( n ) o ( 1 ) 削除o ( 1 )
シングルリンクリストは、ノードのコレクションであり、各ノードは、別のノードまたはnullへのポインタと値を持っています.値は有効なデータ型を指定できます.下記の図に示すようになります.
リンクリストのエントリノードはheadと呼ばれ、最後のノードはtailと呼ばれます.
JavaScriptでは、このようにリンクリストを実装することができます
class Node {
constructor(val) {
this.val = val;
this.next=null
}
}
class SinglyLinkedList{
constructor() {
this.head = null;
this.tail = null;
this.length=0
}
//This method used to push a value to end of the linked list
push(val){
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail=newNode;
}
else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
//this method is used to remove an element from end of linked list.
pop() {
if(!this.head)return undefined
let current = this.head;
let previous = current;
while (current.next) {
previous = current;
current = current.next
}
this.tail = previous
previous.next = null;
this.length = this.length - 1;
if (this.length == 0) {
this.tail = null
this.head=null
}
return this
}
//this method is used to add a value to beginning of a list.
unshift(val) {
let newNode = new Node(val)
if (!this.head) {
this.head = newNode
this.tail=newNode
}
else {
let currentHead = this.head;
newNode.next = currentHead;
this.head=newNode
}
this.length++
return this
}
//this method is used to remove a value from beginning of a list
shift() {
if (!this.head) return undefined;
if (this.length === 1) {
this.head = null;
this.tail = null
}
else {
this.head = this.head.next;
}
this.length--;
return this;
}
//this method is used to get a value from a particular position in list.
get(position) {
if (position < 0 ||position>=this.length) {
return undefined
}
let index = 0;
let currentHead = this.head;
while (position!=index) {
currentHead = currentHead.next;
index++;
}
return currentHead
}
//this method is used to replace a value from a particular position in list.
set(value, position) {
let getValue = this.get(position)
if (!getValue) return false;
getValue.val=value
return this
}
//this method is user to insert an element in the list at a particular position.
insert(position, val) {
if (position < 0 || position > this.length) {
return undefined;
}
if (position === 0) {
return this.unshift(val)
}
else if (position === this.length) {
return this.push(val)
}
let newNode = new Node(val)
let previous = this.get(position - 1)
if (!previous) return false;
let nextEl = previous.next;
newNode.next = nextEl;
previous.next=newNode
this.length++;
return this;
}
//this method is used to remove a value from a particular position
remove(position) {
if (position < 0 || position > this.length) {
return undefined
}
if (position === 0) {
return this.shift(val)
}
else if (position === this.length-1) {
return this.pop(val)
}
let getEl = this.get(position-1)
getEl.next = getEl.next.next;
this.length--;
return this
}
//this method is used to get the size of the list
size(){
return this.length
}
}
リストの利点
シングルリンク一覧
ビッグO表記
Reference
この問題について(単独連結リスト), 我々は、より多くの情報をここで見つけました https://dev.to/siva089/singly-linked-list-piテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol