単独連結リスト

何がシングルリンクスリストですか?
シングルリンクリストは、ノードのコレクションであり、各ノードは、別のノードまたは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表記

アクセスo ( n )

探索o ( n )

o ( 1 )

削除o ( 1 )