JSデータ構造一方向チェーンテーブル

6259 ワード

JAvascriptチェーンテーブル

たんほうこうチェーンテーブル

チェーンテーブルは、規則的に要素の集合を格納しますが、配列とは異なり、チェーンテーブルの要素はメモリに連続的に配置されていません.

各要素は、1つの記憶要素自体のノードと、次の要素への参照(ポインタまたはリンクとも呼ばれる)から構成される.

注意:

は、従来の配列に対して、チェーンテーブルの1つの利点は、要素を追加または除去する際に他の要素を移動する必要がないことである.

しかし、チェーンテーブルはポインタを使用する必要があるため、チェーンテーブルを実装する際には追加の注意が必要である.

配列では、任意の場所の任意の要素に直接アクセスできますが、チェーンテーブルの中間の要素にアクセスするには、必要な要素

が見つかるまで、開始点(ヘッダー)からチェーンテーブルを反復する必要があります.
簡単な例を挙げます.

宝探しゲーム:あなたは1本の手がかりがあって、この手がかりは次の手がかりを探す場所のポインタを指して、このリンクに沿って次の場所に行って、別の1本の次の場所を指す手がかりを得て、チェーンテーブルの中間の手がかりを得る唯一の方法は、起点(第1の手がかり)からチェーンテーブルに沿って

を探すことです

列車:1本の列車は一連の車両から構成され、各車両は互いに接続されている.車両を分離したり、位置を変更したり、追加したり、削除したりしやすいです.各車両はチェーン時計の要素で、車両間の接続はポインタです.

チェーンテーブルクラスメソッド

push(element)/append(element):チェーンテーブルの末尾に新しい要素

を追加

insert(position,element):チェーンテーブルの特殊な位置に新しい要素

を挿入する

get(position):対応する位置の要素

を取得する.

indexOf(element):リスト内の要素のインデックスを返します.リストに要素がない場合は

を返します.

update(positon,element):位置を変更する要素

removeAt(position):リストの特定の場所から

を削除します.

remove(element):リストから

を削除します.

isEmpty():チェーンテーブルに要素が含まれていない場合はtrueが発生し、チェーンテーブルの長さが大きい場合はfalse

が返されます.

size():チェーンテーブルに含まれる要素の数を返します.配列lengthに類似する

実装チェーン:

class LinkedList {
    constructor() {
            this.head = null
            this.length = 0
        }

append(element):チェーンテーブルの末尾にデータ

  append(element) {
          const newNode = new Node(element);
          //      
          if (!this.head) {
              this.head = newNode
          } else {
              let current = this.head;
              while (current.next) {
                  current = current.next
              }
              current.next = newNode
          }
          this.length++
      }

を追加

insert(position,element):チェーンテーブルの特殊な位置に新しい項目

  insert(position, element) {
          //      
          if (position < 0 || position > this.length) return false
              //       
          const newNode = new Node(element)
              //     
          if (position === 0) {
              newNode.next = this.head
              this.head = newNode
          } else {
              let index = 0
              let current = this.head
              let previous = null
              while (index++ < position) {
                  previous = current
                  current = current.next
              }
              previous.next = newNode
              newNode.next = current
          }
          this.length++
              return true
      }

を挿入する.

get(position):対応する位置の要素

  get(position) {
      if (position < 0 || position > this.length - 1) return null
          //         
      let index = 0
      let current = this.head
      while (index++ < position) {
          current = current.next
      }
      return current.element
  }

を取得する.

indexOf(element):リスト内の要素のインデックスを返します.リストに要素がない場合は-1

  indexOf(element) {
          //        
          let current = this.head
          let index = 0
              //     
          while (current) {
              if (current.element === element) {
                  return index
              }
              index++
              current = current.next
          }
          return -1
      }

を返します.

update(positon,element):位置を変更する要素

  update(positon, element) {
          //   position     ，            
          const result = this.removeAt(positon)
          //   position，            
          this.insert(positon, element)
          return result
      }

removeAt(position):リストの特定の位置から

  removeAt(position) {
      if (position < 0 || position > this.length - 1) return null
          //     
      let current = this.head
      let previous = null
      let index = 0
          // 
      if (position === 0) {
          this.head = current.next
      } else {
          while (index++ < position) {
              previous = current
              current = current.next
          }
          previous.next = current.next
      }
      this.length--
          return current.element
  }

を削除する.

remove(element):リストから

  remove(element) {
          //     
          const index = this.indexOf(element)
          if (index === -1) return
              //         
          this.removeAt(index)
      }

を削除します.

isEmpty():チェーンテーブルに要素が含まれていない場合はtrueを犯し、チェーンテーブルの長さが大きい場合はfalse

  isEmpty() {
          return this.length === 0
      }

を返します.

size():チェーンテーブルに含まれる要素の数を返します.配列lengthに類似する

  size() {
      return this.length
  }
}

メソッドが成功したかどうかをテスト

append

のテスト

const linkedList = new LinkedList()
linkedList.append('aaa')
linkedList.append('bbb')
linkedList.append('ccc')
linkedList.append('ddd')

console.log(linkedList)//  length  4   ，  node

テストinsert

linkedList.insert(1, 'abc')
linkedList.insert(3, 'cba')

console.log(linkedList)//  length  6   ，  node

テストposition

console.log(linkedList.get(1))//  abc
console.log(linkedList.get(3))//  cba

テストindexof

console.log(linkedList.indexOf('abc'))//  1
console.log(linkedList.indexOf('cba'))//  3
console.log(linkedList.indexOf('asdsd'))//  -1(       -1)

removeAt

のテスト

console.log(linkedList.removeAt(3))//  cba
console.log(linkedList.removeAt(1))//  abc
console.log(linkedList)//    length  4

update

のテスト

console.log(linkedList.update(1, 'npc'))//  bbb（  ：         ，   undefined，     ，    ）
console.log(linkedList)//   bbb   npc，  length 4

remove

のテスト

linkedList.remove('aaa')
console.log(linkedList)//    length 3

isEmpty

のテスト

console.log(linkedList.isEmpty())//  false

テストsize

console.log(linkedList.size())//  3

[TIL] 2021-08-20

AWSによるServerless単純な導入