iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 3
0

上一篇文章介紹的是陣列,並且定義陣列是由多個相同型別的元素所組成的串列

那麼何謂串列(List)呢?

由許多同類型的元素依照特定的順序,線性排列而成的有序集合。

串列中的元素是有順序性的,兩個元素之間必定有前後的關係,有次序性排列之資料。
反之,集合中的元素就沒有前後之分別。
在日常生活中,像是數字(1~9)、英文字母(A~Z)、季節(春夏秋冬)都是有次序性的資料。


串列實作方式分為循序配置串列鏈結配置串列

  • 循序配置串列(Sequential allocation list),就是將串列的資料循序存進陣列中,將資料存在連續記憶體空間維持串列的順序性。
  • 鏈結配置串列(Linked allocation list),也就是今天的主題鏈結串列 Linked list,可以視為串列+鏈結,串列中的元素不需要實際上佔用連續的記憶體空間,而是利用鏈結(Link)的方式,指向下一個元素的位置,維持串列的順序性。

那為何不直接使用Array,還要用Linked list呢?

設計Array時,資料結構簡單,可隨機存取(Random access),且搜尋方便,易讀取資料,
但是!!!
陣列事先需宣告固定記憶空間,因此要刪除或加入新資料時,造成需要移動大量資料才能完成。


Linked list

Linked list 解決了陣列需要預先知道資料大小的缺點,基本上是以變更鏈結指標的方式儲存資料,資料可以在串列中的任一個位置加入新資料,做刪除資料等動作,在實際需要使用時,才會配置記憶體空間。

實作

題目依然是算出3位學生數學成績的平均值:

import java.util.ArrayList;

public class list 
{
	public static void main(String[] argv)
	{
		LinkNode student1 = new LinkNode(50);
		LinkNode student2 = new LinkNode(64);
		LinkNode student3 = new LinkNode(88);
		
		
		ArrayList <LinkNode> Score = new ArrayList<>();
		Score.add(student1);
		Score.add(student2);
		Score.add(student3);
		
		double sum = 0;
		
		for(int i = 0; i < Score.size(); i++)
		{
			sum = sum + Score.get(i).score;
		}
		
		double average = sum / (Score.size());
		
		System.out.print("average:" + average);
		
	}
	
	public static class LinkNode
	{
		double score;
		
		public LinkNode(double s)
		{
			score = s;
		}
	}

}

輸出結果:

average:67.33333333333333

參考

細談資料結構 第六版
ISBN 978-986-312-014-8


今天看到一句話,有點感觸。

有時候溝通上有落差,是因為雙方沒有在同一個水平上

那就努力讓自己與對方站上同一個高度,共勉之。


上一篇
[Data Structure][Array]
下一篇
[Data Structure][Stack]
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言