iT邦幫忙

2021 iThome 鐵人賽

DAY 4
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 4

【Day4】[資料結構]-鏈結串列Linked List-實作

鏈結串列(Linked List)建立的方法

  • append: 在尾部新增節點
  • insertAt: 在特定位置插入節點
  • removeAt: 刪除特定位置節點
  • remove: 刪除特定資料節點
  • indexOf: 回傳第一個出現指定資料的節點位置,空值則回傳-1
  • isEmpty: 確認是否為空串列
  • size: 串列的長度
  • print: 印出串列所有資料

鏈結串列的介紹可以參考此篇


JavaScript(單向鏈結串列為例)

//Linked List

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

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

  //在尾部插入節點
  append(data) {
    let newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while(current.next){
        current = current.next
      }
      current.next = newNode 
    }
    this.length += 1;
  }

  //特定位置插入節點
  insertAt(index, data) {
    // 確認給的位置是否超出實際總數。
    if (index < 0 || index >= this.length) {
      return null;
    }

    let newNode = new Node(data);
    let current = this.head;
    let previous;
    let count = 0;
    if (index == 0) {
      this.head = newNode;
      newNode.next = this.head;
    } else {
      while(count != index){
        count ++;
        previous = current;
        current = current.next;
      }
      newNode.next = current;
      previous.next = newNode;    
    }
    this.length += 1;
  }

  //刪除特定位置節點
  removeAt(index) {
    if (index < 0 || index >= this.length){
        return false;
    }
    let current = this.head;
    let previous;
    let count = 0;
    if (index === 0) {
      this.head = current.next;
    } else {
      while(count != index){
        count ++;
        previous = current;
        current = current.next;
      }
      previous.next = current.next
    }
    this.length -= 1;
  }
  
  //刪除特定節點
  remove(data) {
    let current = this.head;
    let previos = null;
    while (current != null) {
      if (current.data === data) {
        if (previos == null) {
          this.head = current.next;
        } else {
          previos.next = current.next;
        }
        this.length -= 1;
      }
      previos = current;
      current = current.next;
    }
  }

  //回傳第一個出現此資料節點的位置,若空值則回傳-1
  indexOf(data) {
    let currNode = this.head;
    let count = 0;
    while (currNode) {
      if (currNode.data === data) {
          return count;
      }
      count += 1;
      currNode = currNode.next;
    }
    return -1;
  }
  
  //是否為空串列
  isEmpty() {
    return this.length === 0;
  }
  
  //串列長度
  size() {
    return this.length;
  }

  //印出串列所有資料
  print() {
    const temp = [];
    let currNode = this.head;
    while (currNode) {
      temp.push(currNode.data);
      currNode = currNode.next;
    }
    return temp.join(', ');
  }
}


let ll = new LinkedList();
console.log(ll.isEmpty());//true
ll.append(10);
ll.append(20);
console.log(ll.isEmpty());//false
console.log(ll.print())//"10, 20"
ll.insertAt(1,60);
console.log(ll.print())//"10, 60, 20"
ll.append(20);
console.log(ll.print())//"10, 60, 20, 20"
ll.removeAt(2)
console.log(ll.print())//"10, 60, 20"
ll.remove(20)
console.log(ll.size())//2
console.log(ll.print())//"10, 60"

Python(單向鏈結串列為例)

#Linked List

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self, head=None):
        self.head = head

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)

    def insertAt(self, index, data):
        if index < 0 or index >= self.size():
            return
        node = Node(data)
        current = self.head
        previous = None
        count = 0
        if index == 0:
            self.head = Node(data, node)
        else:
            while count != index:
                count += 1
                previous = current
                current = current.next
            new_node = Node(data, previous.next)
            previous.next = new_node

    def removeAt(self, index):
        if index < 0 or index >= self.size():
            return
        current = self.head
        previous = None
        count = 0
        if index == 0:
            self.head = current.next
        else:
            while count != index:
                count += 1
                previous = current
                current = current.next
            previous.next = current.next

    def remove(self, data, all=False):
        current = self.head
        previous = None
        while current:
            if current.data == data:
                if previous:
                    previous.next = current.next
                    current.next = current
                else:
                    self.head = current.next
                if not all:
                    return
            else:
                previous = current
                current = current.next

    def indexOf(self, data):
        node = self.head
        count = 0
        while node:
            if node.data == data:
                return count
            count += 1
            node = node.next

    def isEmpty(self):
        return self.head is None

    def size(self):
        count = 0
        node = self.head
        while node:
            count += 1
            node = node.next
        return count

    def print(self):
        if not self.head:
            print(self.head)
        node = self.head
        while node:
            end = " -> "
            print(node.data, end=end)
            node = node.next

ll = LinkedList()
print(ll.isEmpty())#True
ll.append(10)
ll.append(20)
print(ll.isEmpty())#False
print(ll.print())#10 -> 20 -> None
ll.insertAt(1,60)
print(ll.print())#10 -> 60 -> 20 -> None
ll.append(20)
print(ll.print())#10 -> 60 -> 20 -> 20 -> None
ll.remove(20)
print(ll.print())#10 -> 60 -> 20 -> None
ll.removeAt(1)
print(ll.print())#10 -> 20 -> None
ll.remove(20)
print(ll.size())#1
print(ll.print())#10 -> None

鏈結串列的介紹可以參考此篇


上一篇
【Day3】[資料結構]-鏈結串列Linked List
下一篇
【Day5】[資料結構]-堆疊Stack
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言