ลิงค์ลิสต์ (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

100

101

102

103

104

105

106

<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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

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.

ใช้เวลาโหลดเว็บเพจ: 113 มิลลิวินาที สูง: 6544 จุด กว้าง: 1264 จุด

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

Thaiall.com

Truehits.net