DIV CSS 佈局教程網

用 JavaScript 實作鏈結串列並加上氣泡排序
編輯:關於JavaScript     

鏈結串列是每個資料結構課程的起點。它用「節點 + 指標」取代連續記憶體,因此插入與刪除不必搬動其他元素。本文用 JavaScript 建立一個可擴充的鏈表,並示範氣泡排序。

一、節點與串列的基本結構

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

function GenericList() {
  this.head = null;
  this.current = null;

  // 輸出所有節點
  this.print = function() {
    this.current = this.head;
    while (this.current != null) {
      alert(this.current.data);
      this.current = this.current.next;
    }
  };

  // 插入到鏈頭
  this.addHead = function(t) {
    var node = new Node();
    node.data = t;
    node.next = this.head;
    this.head = node;
  };
}

addHead 是鏈表最關鍵的操作,三步驟順序不能錯:新節點的 next 指向舊頭 → head 指向新節點。若顛倒順序,舊鏈表就會失去入口。

二、氣泡排序

 function SortList() {
  // 對鏈表做氣泡排序
  this.BubbleSort = function() {
    if (this.head == null || this.head.next == null) return;

    var swapped;
    do {
      this.previous = null;
      this.current = this.head;
      swapped = false;

      while (this.current.next != null) {
        if (this.current.data - this.current.next.data > 0) {
          // 交換相鄰兩節點
          var tmp = this.current.next;
          this.current.next = this.current.next.next;
          tmp.next = this.current;

          if (this.previous == null) {
            this.head = tmp;              // 交換的是頭兩個節點
          } else {
            this.previous.next = tmp;
          }

          this.previous = tmp;
          swapped = true;
        } else {
          this.previous = this.current;
          this.current = this.current.next;
        }
      }
    } while (swapped);
  };
}

SortList.prototype = new GenericList();

這裡的指標操作順序值得細看。交換相鄰兩節點 p 與 q(q 在 p 後面)時:

1. 暫存 q
2. p.next = q.next(讓 p 跳過 q)
3. q.next = p(讓 q 接到 p)
4. 把 q 的前驅節點的 next 指向 q(若 p 是頭節點,則更新 head)

順序錯了就會斷鏈,這是鏈表排序最容易出錯的地方。previous 指標的存在,正是為了處理第 4 步。

三、執行

 (function Main() {
  var sl = new SortList();
  for (var i = 0; i < arguments.length; i++) {
    sl.addHead(arguments[i]);
  }
  alert("未排序的鏈表");
  sl.print();

  sl.BubbleSort();
  alert("已排序的鏈表 從小到大");
  sl.print();
})("1", "2", "3", "4");

注意這裡的資料是字串 "1"、"2"、"3",而氣泡排序用減法比較。字串相減會被隱含轉為數字,因此剛好能運作——但這是巧合而非設計。若資料是 "10" 與 "9",字串比較會出錯,減法則正確。實作時應明確轉型或改用可傳入比較函式的設計。

四、用 class 重寫會清楚得多

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

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

  // 尾端追加,維持插入順序
  append(data) {
    const node = new Node(data);
    if (!this.head) { this.head = node; }
    else {
      let cur = this.head;
      while (cur.next) cur = cur.next;
      cur.next = node;
    }
    this.size++;
    return this;
  }

  // 氣泡排序,使用比較函式而非硬編碼減法
  bubbleSort(compare = (a, b) => a - b) {
    if (!this.head || !this.head.next) return this;

    let swapped;
    do {
      swapped = false;
      let prev = null;
      let cur = this.head;

      while (cur.next) {
        if (compare(cur.data, cur.next.data) > 0) {
          const next = cur.next;
          cur.next = next.next;
          next.next = cur;
          if (prev) prev.next = next; else this.head = next;
          prev = next;
          swapped = true;
        } else {
          prev = cur;
          cur = cur.next;
        }
      }
    } while (swapped);

    return this;
  }

  toArray() {
    const result = [];
    for (let cur = this.head; cur; cur = cur.next) result.push(cur.data);
    return result;
  }
}

const list = new LinkedList();
[5, 3, 8, 1, 9, 2].forEach(n => list.append(n));
console.log(list.toArray());        // [5,3,8,1,9,2]
list.bubbleSort();
console.log(list.toArray());        // [1,2,3,5,8,9]

五、幾點實務提醒

print 用 alert 不適合除錯。改用 toArray 加 console.log,能一次看清整個結構,也不必反覆關閉彈窗。

addHead 會反轉順序。依序傳入 1、2、3、4 之後,串列實際是 4→3→2→1。若你要維持輸入順序,應該用 append(如上)或先在陣列反轉。

氣泡排序在鏈表上其實不划算。鏈表沒有隨機存取能力,氣泡排序的優勢(可提前結束)還在,但整體仍是 O(n²)。若真要排序鏈表,合併排序(merge sort)才是正解——它只需 O(n log n),且不需要額外的陣列空間,非常適合鏈表。

至於 JavaScript 的實務:除非在解題或特殊場景,日常開發幾乎用不到自己實作的鏈表,陣列與 Map 已足夠應付絕大多數需求。這個練習的價值在於理解指標操作與資料結構的底層思維。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved