ลิงค์ลิสต์ (Linked List)

ปรับปรุง : 2566-01-20 (ปรับรุ่นเป็น 9.0)

ลิงค์ลิสต์ (Linked List)

ลิงค์ลิสต์ (Linked List) หรือรายการ คือ ชุดของข้อมูลที่มีการจัดเก็บข้อมูลแบบเชื่อมต่อกันเป็นเชิงเส้น แต่ละข้อมูลเรียกว่า อีลิเมนต์ (Element) หรือสมาชิก (Member) ซึ่งสมาชิกประกอบด้วย ข้อมูล (Data) และลิงค์ (Link) โดยลิงค์ของข้อมูลหนึ่งจะเชื่อมไปยังอีกข้อมูลหนึ่ง ทำให้เกิดสายการเชื่อมโยงข้อมูลที่เรียงต่อกันแบบรายการ และข้อมูลอาจประกอบด้วยหลายเขตข้อมูล

ฟังก์ชันการดำเนินงานบนลิสต์ 10 ฟังก์ชัน [3]p.98
1. Create list
2. Insert Node
3. Delete Node
4. Search List
5. Retrieve Node
6. Empty List
7. Full List
8. List Count
9. Traverse List
10. Destroy List
Data Structures: A Pseudocode Approach with C : หน้า 209 ใน Text เหมือนหนังสือ [3]p.114 Empty List
comedu.nstru.ac.th : Linked%20List%20Algorithm%20(1).pdf
codeforwin.com : Data Structures Tutorials
geeksforgeeks.com : C , CPP , Java , Python , C#

Code : Data Structures

ตัวอย่าง

JavaScript may not have pointers but it has everything you need to construct sophisticated data structures (โครงสร้างข้อมูลที่ซับซ้อน) if you think about things in the right way. In this article we implement a classical linked list structure.
ทดสอบ script ได้ที่ w3schools.com

Script from : http://i-programmer.info

<script>
/* 1 create new blank list */
var list=new List();

/* 2 add A B C D */
for(var i=65;i<=68;i++){
 list.add(i);
 document.write(String.fromCharCode(i));
};

/* 3 Main process */
list.delete(65);
list.each(); // BCD
list.insertAsFirst(65);
list.insertAfter(68,69);
list.each(); // ABCDE
document.write(list.item(2).data); // 66

/* 4 Function have 8 methods */
function List() {
 /* a) create blank node */
 List.makeNode = function() {
  return {data: null, next: null};
 };
 
 /* b) start,end point to null */  
 this.start = null;
 this.end = null;

 /* c) create new node */  
 this.add = function(data) {
  if (this.start === null) {
   this.start = List.makeNode();
   this.end = this.start;
  } else { 
   this.end.next = List.makeNode();
   this.end = this.end.next;
  } ;
  this.end.data = data;
 };
 
 /* d) delete a node , find it */   
 this.delete = function(data) {
  var current = this.start;
  var previous = this.start;
  while (current !== null) {
   if (data === current.data) {
    if (current === this.start) {
     this.start = current.next;
     return;
    }
    if (current === this.end) this.end = previous;
    previous.next = current.next; 
    return;
   }
   previous = current;
   current = current.next;
  }
 };
 
 /* e) add before first node */    
 this.insertAsFirst = function(data) {
  var temp = List.makeNode();
  temp.next = this.start;
  this.start = temp;
  temp.data = data;
 };

 /* f) add after a node */    
 this.insertAfter = function(t, data) {
  var current = this.start;
  while (current !== null) {
   if (current.data === t) {
    var temp = List.makeNode();
    temp.data = data;
    temp.next = current.next;
    if (current === this.end) this.end = temp;
    current.next = temp;
    return;
   }
   current = current.next;
  }
 };

 /* g) retrieve node value by seq index */    
 this.item = function(i) {
  var current = this.start;
  while (current !== null) {
   i--;
   if (i === 0) return current;
   current = current.next;
  }
  return null;
 };

 /* h) write each node on document */    
 this.each = function(f) {
  document.writeln("<br/>");
  var current = this.start;
  while (current !== null) {
   document.write(String.fromCharCode(current.data));
   current = current.next;
  }
 };
}
</script>

Output
-----------------
ABCD
BCD
ABCDE66

Sample code
-----------------
/* 1 data type */
var node1 = {
 data:null,
 next:null
};

/* 2 assign value */
node1.data="tom";

/* 3 data type */
var node2={
 data:null,
 next:null
};

/* 4 link 2 node */
node2.data = "jack";
node1.next = node2;

/* 5 diagram */
node1
 [data]-> data1
 [next]-> node2
           [data]-> data2
           [next]-> null

/* 6 write each node */		   
while (node !== null) {
   write(node.data);
   node = node.next;
}

Tryit.asp?filename=tryhtml_basic

Data Structures: A Pseudocode Approach with C Data Structures: A Pseudocode Approach with C : หน้า 209 ใน Text เหมือนหนังสือ [3]p.114 Empty List
comedu.nstru.ac.th : Linked%20List%20Algorithm%20(1).pdf

Algorithm createList (list)
	Initializes metadata for list.
		Pre 	list is metadata structure passed by referece
		Post metadata initiazed
	1 allocate (list)
	2 set list head to null
	3 set list count to 0
End createList
Algorithm insertNode(list, pPre, dataIn)
	Inserts data into a new node in the list.
		Pre 	list is metadata structure to a valid list
				pPre is pointer to data’s logical predecessor
				dataIn contains data to be inserted
		Post 	data have been inserted in sequence
		Return 	true if successful. False if memory overflow
	1 allocate (pNew)
	2 set pNew data to dataIn
	3 if (pPre null)
		Adding before first node or to empty list.
		1 set pNew link to list head
		2 set list list head to pNew
	4 else
		Adding in middle or at end.
		1 set pNew link to pPre link
		2 set pPre link to pNew
	5 end if
	6 return true
End insertNode
Algorithm deleteNode (list, pPre, pLoc, dataOut)
	Deletes data from list & returns it to calling module.
		Pre 	list is metadata structure to a valid list
				pPre is poiter to predecessor node
				pLoc is a pointer to node to be deleted
				dataOut is variable to receive deleted data
		Post 	data have been deleted and returned to caller
	1 move pLoc data to dataOut
	2 if (pPre null)
		Deleting furst node
		1 set list head to pLoc link
	3 else
		Deleting other nodes
		1 set pPre link to pLoc link
	4 end if
	5 recycle (pLoc)
end deleteNode
Algorithm searchList (list, pPre, pLoc, target)
	Searches list ad passes back address of node containing Target and its logical predecessor.
		Pre 	list is metadata structure to a valid list
				pPre is pointer variable for predecessor
				pLoc is pointer variable for current node
				target is the key being sought
		Post 	pLoc points to first node with equal/greather key
				-or- null if target > key of last node
				pPre points to largest node smaller than key
				-or- null if target < key of fiest node
		Return 	true if found, false if nod found
	1 set pPre to null
	2 set pLoc to list head
	3 loop (pLoc nod null AND target > pLoc key)
		1 set pPre to pLoc
		2 set pLoc to pLoc link
	4 end loop
	5 if (pLoc null)
		Set return value
		1 set found to true
	6 else
		1 if (target equal pLoc key)
			1 set found to true
		2 else
			1 set found to false
		3 end if
	7 end if
	8 return found
End searchList
Algorithm retreveNod (list, key, dataOut)
	Retrieves data from a list.
		Pre 	list is metadata structure to a valid list
				Key is target of data to be retrieved
				dataOut is variable to receive data
		Post 	data placed in dataOut
				-or- error returned if not found
		Return 	true if successful, false if data not found
	1 set found to searchList (list, pPre, pLoc, key)
	2 if (found)
		1 move pLoc data to dataOut
	3 end if
	4 return found
end retrieveNode
Algorithm emptyList (list)
	Returns Boolean indicating whether the list is emply.
		Pre 	list is metadata structure to a valid list
		Return 	true if list empty, false if list contains data
	1 if (list count equal 0)
		1 return true
	2 else
		1 return false
end emptyList
Algorithm fullList (list)
	Returns Boolean indicating whether or not the list is full.
		Pre 	list is metadata structure to a valid list
		Return 	false if room for ew node; true if memory full
	1 if (memory full)
		1 return true
	2 else
		1 return false
	3 end if
	4 return true
end fullList
Algorithm listCount (list)
	Returns integer representing number of nodes in list.
		Pre 	list is metadata structure to a valid list
		Return 	count for number of nodes in list
	1 return (list count)
end listCount
Algorithm getNext (list, fromWhere, dataOut)
	Traverses a list. Each call returns the location of an element in the list.
		Pre 	list is metadata Structure to a valid list
				FromWhere is 0 to start at the first element
				dataOut is reference to data variable
		Post 	dataOut contains data and true returned
				-or- if end of list, returns false
		Return 	true if next element located
				false if end of list
	1 if (empty list)
		1 return false
	2 if (fromWhere is beginning)
		Start from first
		1 set list pos to list head
		2 move current list data to dataOut
		3 return true
	3 else
		Continue from pos
		1 if (end of list)
			End of list
			1 return false
		2 else
			1 set list pos to next node
			2 move current list data to node
			3 return true
		3 end if // added in [3]
	4 end if
end getNext
Algorithm destroyList (pList) // [3]p.118
	Deletes all data in list.
		Pre 	list is metadata structure to a valid list
		Post 	all data deleted
	1 loop (not at end of list)
		1 set list head to successor node
		2 release memory to heap
	2 end loop
		No data left in list. Reset metadata.
	3 set list pos to null
	4 set list count to 0
end destroyList

เอกสารฉบับเต็ม (Full Text)

รศ.ดร.สมชาย ประสิทธิ์จูตระกูล

Mark Allen Weiss

A Byte of Python

เอกสารอ้างอิง (Reference) [1] นิรุธ อำนวยศิลป์, "โครงสร้างข้อมูล : การเขียนโปรแกรมและการประยุกต์", บริษัท ดวงกมลสมัย จำกัด., กรุงเทพฯ, 2548.
[2] Guy J.Hale, Richard J.Easton, "Applied Daa Structures Using Pascal", D.C.Heath and Company. Canada. 2530.
[3] โอภาส เอี่ยมสิริวงศ์, "โครงสร้างข้อมูล (Data Structures) เพื่อการออกแบบโปรแกรมคอมพิวเตอร์", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2549.
[4] วิวัฒน์ อภิสิทธิ์ภิญโญ, อมร มุสิกสาร, "โครงสร้างข้อมูล (Data Structures)", บริษัท เอ-บุ๊ค ดิสทริบิวชั่น จำกัด., กรุงเทพฯ, 2548.
[5] เนรมิต ชุมสาย ณ อยุธยา, "เรียนรู้โครงสร้างข้อมูลและอัลกอริทึมด้วย Java", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2550.
[6] ขนิษฐา นามี, "โครงสร้างข้อมูลและอัลกอริทึม", บริษัท ไอดีซี อินโฟ ดิสทริบิวเตอร์ เซ็นเตอร์ จำกัด., กรุงเทพฯ, 2548.
[7] Michael McMillan, "Data Structures and Algorithms with JavaScript", O’Reilly Media, Inc., USA., 2014.
[8] Loiane Groner, "Learning JavaScript Data Structures and Algorithms", Packt Publishing, 2014.

"ไม่เริ่มต้นในวันนี้ จะไม่มีทางสำเร็จในวันพรุ่ง" โดย โยฮัน ว็อล์ฟกัง ฟ็อน เกอเทอ

Thaiall.com

Truehits.net