iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 18
0
自我挑戰組

透過JavaScript學習演算法與資料結構系列 第 18

連結串列(Linked List)

  • 分享至 

  • xImage
  •  

連結串列是一種方便新增刪除的資料結構,陣列在記憶體中是連續的放置資料,而連結串列並不是,它透過指標維持資料的連續性。

img

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

  add(element) { 
    const node = new Node(element); 
    let current; 
    if (this.head == null){
      this.head = node; 
    }
    else { 
      current = this.head; 
      while (current.next) { 
        current = current.next; 
      } 
      current.next = node; 
    } 
    this.size++; 
  }

  insertAt(element, index) 
  { 
    if (index > 0 && index > this.size){
      return false; 
    }
    else { 
      const node = new Node(element); 
      let curr, prev; 
      curr = this.head; 
      if (index == 0) { 
        node.next = head; 
        this.head = node; 
      } else { 
        curr = this.head; 
        let i = 0; 
        while (i < index) { 
          i++; 
          prev = curr; 
          curr = curr.next; 
        } 
        node.next = curr; 
        prev.next = node; 
      } 
      this.size++; 
    } 
  }

  removeFrom(index) { 
    if (index > 0 && index > this.size){
      return -1; 
    }
    else { 
      let curr, prev, it = 0; 
      curr = this.head; 
      prev = curr; 
      if (index === 0) { 
        this.head = curr.next; 
      } else { 
        while (it < index) { 
          it++; 
          prev = curr; 
          curr = curr.next; 
        }
        prev.next = curr.next; 
      } 
      this.size--; 
      return curr.element; 
    } 
  } 

  removeElement(element) { 
    let current = this.head; 
    let prev = null; 

    while (current != null) { 
      if (current.element === element) { 
        if (prev == null) { 
          this.head = current.next; 
        } else { 
          prev.next = current.next; 
        } 
        this.size--; 
        return current.element; 
      } 
      prev = current; 
      current = current.next; 
    } 
    return -1; 
  } 

  indexOf(element) { 
    let count = 0; 
    let current = this.head; 
    while (current != null) { 
      if (current.element === element){
        return count; 
      }
      count++; 
      current = current.next; 
    } 
    return -1; 
  }

  isEmpty() { 
    return this.size == 0; 
  }

  getSize(){ 
    console.log(this.size); 
  }

  printList() { 
    let curr = this.head; 
    let str = ""; 
    while (curr) { 
      str += curr.element + " "; 
      curr = curr.next; 
    } 
    console.log(str); 
  }
} 

程式碼


上一篇
堆疊(Stack)
下一篇
樹(Tree)
系列文
透過JavaScript學習演算法與資料結構30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言