單向鏈結串列(Singly linked list)

整理

單向鏈結串列(Singly linked list)示意圖

每一個節點內含
next // 儲存下一個的節點
val // 數值

如果該節點next為null代表已經沒有下個節點串接。

如上圖範例:
數值為12節點的下個節點(next)，接數值為99節點
數值為99節點的下個節點(next)，接數值為37節點
而數值37節點的下個節點(next)，表示沒有結點串接為null

Big-O
search 搜尋 O(N)

特點
只能做循序存取 (Sequential access)

C#程式碼

using System;

//節點
public class LinkNode
{
   public int val;
   public LinkNode next;
   public LinkNode(int val,LinkNode next){
	   this.val = val;
	   this.next = next;
   }
   public LinkNode(int val){
	   this.val = val;
	   this.next = null;
   }
};

public class Program
{
	// SingleLinkList 串接節點
	public static void Main()
	{
	
		LinkNode node1 = new LinkNode(12); 
		LinkNode node2 = new LinkNode(99); 
		LinkNode node3 = new LinkNode(37); 
		
		node1.next = node2; // 綁定node1的尾端接node2
		node2.next = node3; // 綁定node2的尾端接node3
		
	
		Console.WriteLine("手動印出節點:");
		Console.WriteLine(node1.val); // 節點1
		Console.WriteLine(node1.next.val);// 節點2 (節點1的下1個元素)
		Console.WriteLine(node1.next.next.val);// 節點3 (節點1的下2個元素)
		if(node1.next.next.next == null){ //節點4，尾端沒串接任何資料為null
			Console.WriteLine("null");
		}
		
		Console.WriteLine("遍歷節點:");
		LinkNode currentNode = node1;
		while(currentNode != null){ // null表示為末端
			Console.WriteLine(currentNode.val);
			// 將當前節點指到下個節點
			currentNode = currentNode.next;
		}
		
		Console.WriteLine("在節點1末端添加一個數值38的節點:");
		
		LinkNode cursor = node1; 
		LinkNode newNode = new LinkNode(38);
		
		// 添加節點在最後面
		while(true){
			if(cursor.next == null){ 
				cursor.next = newNode; // 找到最尾端把null指派成新節點38
				break;
			}else{
				cursor = cursor.next; //不斷往下找節點
			}
		}
		
		Console.WriteLine(node1.next.next.next.val); //Q1:可取得38，這邊其實我有些不懂，是new參考的關係嗎，為什麼能夠改到node1?
	}
}

結果:

手動印出節點:
12
99
37
null
遍歷節點:
12
99
37
在節點1末端添加一個數值38的節點:
38

目前有標記的Q1是現在不懂的地方，是new參考的關係嗎，為什麼能夠改到node1的值?
按照這篇來說，他指出C#只有call by value、call by address。
https://dotblogs.com.tw/daniel/2018/02/26/150443

在C#廣義來說
基本型別 Struct (int,double,float,byte ...)  可看作 傳值
一般型別 Class (自訂Class ,SqlConnectio....)  可看作 傳址  更精確來說是傳Stack的值(指向Heap的記憶體位置)

沒傳參考，只有傳值和傳址，所以Q1可能是因為把node1當時的記憶體位置指派給cursor，所以就代表著node1的位置。
而直到最後終端null時，在把new出來的節點38的位址接上去。
把記憶體位置傳到另一個記憶體位置的值上

參考資料
https://kopu.chat/2017/06/02/c-%e8%aa%9e%e8%a8%80%ef%bc%9a%e9%8f%88%e7%b5%90%e4%b8%b2%e5%88%97linked-list%e7%9a%84%e5%bb%ba%e7%ab%8b%e8%88%87%e5%88%aa%e9%99%a4/
https://en.wikipedia.org/wiki/Linked_list
https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8