Data Structure - Array

DataStructure 10 minutes read (About 1487 words)

Array 陣列

Array 是最簡單也最被廣泛使用的資料結構，幾乎所有程式語言都具備陣列這個資料結構，
以定義來說，他是由相同類型的元素（element）的集合所組成的資料結構，在一般程式語言中陣列只能儲存同樣型別的值，但在 JavaScript 則可以儲存不同型別的值（也應該盡量避免）。

優點：

lookup： 只需要利用 index 即可對特定位置的資料作存取與查詢，此動作之時間複雜度為 O(1)
push： 資料到最尾端時也只要時間複雜度 O(1)

缺點：

insert、 delete： Array 的元素在記憶體中是連續儲存的，所以假設要新增或刪除 Array 的第1個位置的元素，則須將第2~last 位置的元素一一往前或往後搬動，時間複雜度為 O(n)

使用時機 :

  • 希望能夠快速存取查詢資料，時間複雜度只有 O(1)。

  • 已知欲處理的資料數量，便能確認 Array 的大小。
    #在 JavaScript 中的 Array 是 Dynamic Array，動態分配陣列大小可能會導致搬移 O(n)

  • 要求記憶體空間的使用越少越好。

Javascript 陣列：

建立 class

1
2
3
4
5
6
class MyArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }
}

get

1
2
3
4
5
6
class MyArray {
  //...以上省略
  get(index) {
      return data[index];
  }
}

push

1
2
3
4
5
6
7
8
class MyArray {
  //...以上省略
  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }
}

pop

1
2
3
4
5
6
7
8
9
class MyArray {
  //...以上省略
  pop() {
    const lastItem = this.data[length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem;
  }
}

delete

1
2
3
4
5
6
7
8
class MyArray {
  //...以上省略
  delete(index) {
    const item = this.data[index];
    this.shiftItems(index);
    return item;
  }
}

shift

1
2
3
4
5
6
7
8
9
10
class MyArray {
  //...以上省略
  shiftItems(index) {
    for(let i = index; i < this.length - 1; i++){
      this.data[i] = this.data[i+1];
    }
    delete this.data[this.length - 1];
    this.length--;
  }
}

陣列在 JavaScript 上內建的方法

新增陣列

  • 使用 new Array()，可以自定陣列大小

    1
    2
    3
    let newArr1 = new Array();
    let newArr2 = new Array(999);
    let students = new Array('阿諾史瓦辛格', '席維斯史特龍');

  • 使用 [] 宣告陣列

    1
    2
    let newArr1 = [];
    let students = ['阿諾史瓦辛格', '席維斯史特龍'];

push 、 pop 、 unshift 、 shift

  • 使用 push、pop 新增或移除最後陣列元素：

    1
    2
    3
    4
    5
    6
    7
    let students = ['阿諾史瓦辛格', '席維斯史特龍', '馮迪索'];

    // 將 巨石強森 加入最後元素 
    students.push('巨石強森'); // ['阿諾史瓦辛格', '席維斯史特龍', '馮迪索', '巨石強森']

    // 將剛剛加入的 巨石強森 移除
    students.pop(); // ['阿諾史瓦辛格', '席維斯史特龍', '馮迪索']

  • 將元素插入陣列首位 和 移除首位的元素 unshift、shift ：

    1
    2
    3
    4
    5
    6
    7
    let students = ['阿諾史瓦辛格', '席維斯史特龍', '馮迪索'];

    // 將 巨石強森 插入首位
    students.unshift('巨石強森'); // ['巨石強森', '阿諾史瓦辛格', '席維斯史特龍', '馮迪索']

    // 將剛剛加入的 巨石強森 移除
    students.shift(); // ['阿諾史瓦辛格', '席維斯史特龍', '馮迪索']

二維陣列

在 JavaScript 中只其實只支援一維陣列，但是可以用陣列嵌套陣列的方式來模擬多維陣列：

1
2
3
4
5
6
7
8
9
10
let students = [];
students[0] = ['巨石強森', '阿諾史瓦辛格'];
students[1] = ['席維斯史特龍', '馮迪索'];
// students = [['巨石強森', '阿諾史瓦辛格'], ['席維斯史特龍', '馮迪索']]

for(let i = 0; i < students.length; i++) {
    for(let j = 0; j < students[i].length; j++) {
        console.log(students[i][j]); // 巨石強森 阿諾史瓦辛格 席維斯史特龍 馮迪索
    }
}

常用陣列方法

陣列迭代

  • forEach，單純對陣列每個元素都進行迭代

    1
    2
    3
    numbers.forEach(function(value, index){
    	console.log(value, index);
    });

  • map，對陣列每個元素都進行迭代並回傳新的陣列，不會改變原本陣列。

    1
    2
    3
    4
    5
    6
    7
    let numbers = [1, 2, 3, 4];

    let newNumbers = numbers.map(function(value, index) {
    	return value + 1
    });
    console.log(numbers); // [1, 2, 3, 4]
    console.log(newNumbers); // [2, 3, 4, 5]

  • every，對陣列每個元素都進行迭代，若迭代函數內容皆為 true，則回傳 true，反之回傳 false

    1
    2
    3
    4
    5
    6
    7
    let ages = [32, 33, 16, 40];

    function checkAdult(age) {
      return (age >= 18) ? true : false;
    }

    console.log(ages.every(checkAdult)); // false

  • some，若迭代函數中有一個為 true 即回傳 true，反之回傳 false

    1
    2
    3
    4
    5
    6
    7
    let ages = [3, 10, 18, 20];

    function checkAdult(age) {
      return (age >= 18) ? true : false;
    }

    console.log(ages.some(checkAdult)); // true

  • reduce，由左向右累加，參數有四個 previousValue,currentValue, index, array

    1
    2
    3
    4
    5
    6
    let numbers = [2, 3, 5, 6];

    function getSum(total, num) {
      return total + num;
    }
    console.log(numbers.reduce(getSum)); // 16

  • reduceRight，由右向左累加

    1
    2
    3
    4
    5
    6
    let numbers = [2, 3, 5, 6];

    function getSum(total, num) {
      return total + num;
    }
    console.log(numbers.reduce(getSum)); // 16

  • filter，依據條件回傳過濾後的陣列

    1
    2
    3
    4
    5
    6
    7
    let ages = [32, 33, 16, 40];

    function checkAdult(age) {
      return age >= 18;
    }

    console.log(ages.filter(checkAdult)); // [32, 33, 40]

搜尋

  • indexOf，搜尋第一個匹配到的元素的 index

    1
    2
    let students = ['阿諾史瓦辛格', '席維斯史特龍', '馮迪索', '巨石強森'];
    let a = students.indexOf('馮迪索'); // 2

  • lastIndexOf，搜尋最後一個匹配到的元素的 index

    1
    2
    let students = ['阿諾史瓦辛格', '席維斯史特龍', '馮迪索', '巨石強森','馮迪索'];
    let a = students.indexOf("Orange"); // 4

排序

  • sort，將陣列內容進行排序，回傳排序後陣列，若為文字則根據 ASCII Code 編碼大小進行比較

    1
    2
    let fruits = ["Banana", "Orange", "Apple", "Mango"];
    fruits.sort(); // ["Apple", "Banana", "Mango", "Orange"]

  • reverse，將陣列內容反轉

    1
    2
    let fruits = ["Banana", "Orange", "Apple", "Mango"];
    fruits.reverse(); // ["Mango", "Apple", "Orange", "Banana"]

陣列合併和切割

  • join，將陣列轉成字串，預設以分隔符號,串連成字串

    1
    2
    3
    4
    5
    let fruits = ['Banana', 'Orange', 'Lemon', 'Apple', 'Raspberry'];
    console.log(fruits.join()); // Banana,Orange,Lemon,Apple,Raspberry

    let fruits = ['Banana', 'Orange', 'Lemon', 'Apple', 'Raspberry'];
    console.log(fruits.join('')); // BananaOrangeLemonAppleRaspberry

  • toString，回傳陣列轉成字串的結果，不會改變原本陣列，類似 join，但是只能用預設 , 做分隔

    1
    2
    let fruits = ["Banana", "Orange", "Apple", "Mango"];
    fruits.toString();	// Banana,Orange,Apple,Mango

  • split，將字串轉成陣列

    1
    2
    let a = '1,2,3,4';
    console.log(a.split(',')); //["1", "2", "3", "4"]

  • concat，合併陣列

    1
    2
    3
    let hege = ["Cecilie", "Leo"];
    let stale = ["Emil", "May", "Linus"];
    console.log(hege.concat(stale)); // ['Cecilie', 'Leo', 'Emil', 'May', 'Linus']

  • slice，剪裁並回傳新的陣列

    1
    2
    let fruits = ['Banana', 'Orange', 'Lemon', 'Apple', 'Raspberry'];
    console.log(fruits.slice(1, 3)); // ['Orange', 'Lemon', 'Apple']

#JavaScript #DataStructure
Data Structure - Linked List JavaScript - Value vs. Reference

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×