home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / LLIST.NTS < prev    next >
Text File  |  1997-07-05  |  9KB  |  178 lines
  1. +++Date last modified: 05-Jul-1997
  2.  
  3. === Some notes on Linked Lists ===========================================
  4.  
  5. Introduction
  6.  
  7. Linked lists consist of any number of 'nodes' which contain data and one
  8. pointer for singly linked lists or two pointers for doubly linked lists.
  9. The first or only pointer serves to connect one node to a next node; in a
  10. doubly linked list the second pointer serves to connect the node to a
  11. previous node.
  12. A 'first node pointer' serves as anchor to the entire list. A 'last node
  13. pointer' is optional; but it is common in doubly linked lists.
  14. One or more 'current node pointers' -- sometimes allocated on the fly --
  15. simplify access to specific nodes.
  16.  
  17. The three most common operations on linked lists are:
  18. - creating a new node AFTER the current node,
  19. - creating a new node BEFORE the current node,
  20. - deleting the current node.
  21.  
  22. Operations to create a node as first or last node, or deleting a first or
  23. last node are also common. And of course there are operations to change
  24. the current node -- i.e. changing the value of the current node pointer --
  25. and operations to access the data of the current node and optionally the
  26. data of the first or last nodes.
  27.  
  28.  
  29. Singly Linked Lists, simple design and complicated implementation
  30.  
  31. Generally speaking, creating a new node AFTER the current node is rather
  32. simple. It consists of:
  33. - allocating an appropriately sized piece of memory for a node,
  34. - filling in its data part (actually optional: it could be done later),
  35. - copying the value of the current node's next node pointer to the new
  36.   node's next pointer,
  37. - copying the address of the new node to the current node's next pointer,
  38. - optionally changing the current node pointer's value to the address of
  39.   the new node.
  40.  
  41. Creating a new node BEFORE the current node is also rather simple:
  42. - make the preceding node the current node,
  43. - then insert the new node after the current node.
  44.  
  45. And deleting the current node:
  46. - copy the value of the current node's next pointer to the preceding
  47.   node's next pointer,
  48. - de-allocate the current node's piece of memory,
  49. - change the current node pointer in a sensible way, e.g. change it to the
  50.   address of the next node.
  51.  
  52. There are, however, a number of problems:
  53. 1 The obvious first is the necessity to find the preceding node when you
  54.   want to delete the current node, and when you want to create a new node
  55.   before the current node.
  56. 2 What will be the value of the current node pointer after deletion of the
  57.   first node or the last node -- both in the sense of 'only' node and
  58.   'end-of-the-list' node?
  59. 3 What special things should be done when the list is empty?
  60. 4 What special handling is necessary when creating a new node _before_ the
  61.   current node when the current node is the _first_ node?
  62. 5 What special handling is necessary when creating a new node _after_ the
  63.   current node when the current node is the _last_ node?
  64.   (This 'problem' is included for symmetry reasons. The answer is: "None,
  65.   unless a 'last node pointer' and/or a dummy head node are used.")
  66. 6 What are the consequences of allowing the current node pointer to become
  67.   invalid? For example after deleting the last node (see 2), or after
  68.   changing the current node pointer to the 'next' node if it was pointing
  69.   to the last node. (See also 4 and 5.)
  70.  
  71. In a simple design these problems should be handled when the situations
  72. occur. Note that for some special purpose designs some of these problems
  73. can be ignored.
  74.  
  75. Singly Linked Lists, complicated design and simple implementation I
  76.  
  77. Problem 6 can be handled by taking care that it does not occur.
  78. After deletion of a node the current node pointer is commonly set to point
  79. to the node following the old current node. If after deletion of the last
  80. (end-of-list) node the new current node is set to be the node preceding
  81. the deleted node, the problem is avoided.
  82. This complicates the implementation for deletion of a node slightly, but
  83. it simplifies the implementation for creating a new node after the current
  84. node -- and optionally the implementation for creating a new node at the
  85. end of the list -- as the situation does not need to be detected and
  86. handled any more. In a good implementation it does not affect the code for
  87. changing the current node pointer to the next node. (One of my first
  88. implementations wasn't good in that respect ...)
  89. Note that this solution for Problem 6 also partially solves Problem 2. And
  90. essentially merges the remaining part of Problem 2 with Problem 3.
  91. Note also that the solution may have some unwanted side effects as the
  92. 'motion' of the current node pointer will be reversed at the end of the
  93. list.
  94.  
  95. Singly Linked Lists, complicated design and simple implementation II
  96.  
  97. Problem 2 can be handled by giving node pointers a NULL value as indica-
  98. tion of its pointing to an 'invalid' node. An alternative is using other
  99. 'invalid' pointer values. With invalid meaning that the data at that
  100. address is irrelevant. But the 'invalidity' must usually be detectable!
  101. Note however that whenever detection is required, a NULL value is the most
  102. efficient. But when detection is NOT required another value may be better.
  103.  
  104. Singly Linked Lists, complicated design and simple implementation III
  105.  
  106. Problem 3 can be handled with a dummy head node. I.e. a node which is the
  107. physical first node, but does NOT contain relevant data. For practical
  108. purposes the node following this node is the actual or logical first node.
  109. Now let the current node pointer have a similar extra level of indirection
  110. -- otherwise it wouldn't make any sense. Also the current node pointer
  111. itself does not have then to be updated in come cases. As there is now no
  112. more structural difference between the logical first node and any other
  113. node Problem 3 is completely solved. As is a part of problem 4.
  114. Note that implementation for creating a new node BEFORE the current node
  115. now 'physically' is a _simplified_ version of the implementation for
  116. creating a new node AFTER the current node without a dummy head node. And
  117. that the implementation for creating a new node AFTER the current node is
  118. merely a matter of changing the value of the current node pointer to the
  119. address of the next node -- IF POSSIBLE -- and creating it before the now
  120. current node.
  121. Note also that Problem 1 -- with exception of deletion of the last node --
  122. is completely solved. And that the remaining problem with deletion of the
  123. last node is actually the same as Problems 6 AND 5.
  124. When having a valid last node pointer is useful Problem 6 should be solved
  125. as indicated. In my opinion it should always be solved, as the performance
  126. penalty is quite low.
  127.  
  128. Singly Linked Lists, conclusion
  129.  
  130. For general purpose implementations of Singly Linked Lists, it is very
  131. sensible to use a dummy head node. As an extra level of indirection is
  132. added there is a slight performance penalty. On the other hand the code
  133. size is definitely reduced, and the performance advantage -- by not having
  134. to test for special conditions -- may be more than the penalty.
  135.  
  136. For special purpose Singly Linked Lists the choice of whether or not to
  137. use dummy head nodes is quite dependent on its purpose and on performance
  138. requirements.
  139.  
  140. In the literature (Sedgewick, _Algorithms in C_, ISBN 0-201-51425-7, p.20)
  141. it is suggested that having a dummy tail node as well is useful.
  142. This is however only the case when the environment has 'garbage collec-
  143. tion' capabilities. I.e. it is useful only when explicit de-allocation of
  144. memory is not necessary (or even possible). Without garbage collection, or
  145. without a way to reverse a de-allocation, it causes MORE problems than it
  146. solves!
  147. The same book also suggests having the last (the dummy if it is used) node
  148. pointing to itself. That only makes sense in some special implementations.
  149. It has the advantage of not requiring a test to prevent the current node
  150. pointer from 'leaving' the list. But as this test is required anyway in
  151. most implementations and environments, it normally does not make any
  152. sense.
  153.  
  154.  
  155. Doubly Linked Lists
  156.  
  157. The operations relevant to Doubly Linked Lists are essentially the same as
  158. those for Singly Linked Lists. Only the 'previous node pointers' need to
  159. be handled in addition.
  160. The problems are generally also the same. Only Problem 1 isn't there any
  161. more. Doubly Linked Lists are a specific solution to that problem! The
  162. only new questions are whether there should be a last node pointer and
  163. whether there should be a dummy tail node as well. The answer to which is:
  164. neither or both.
  165.  
  166. Dummy head nodes are as useful in Doubly Linked Lists as they are in
  167. Singly Linked Lists and for the same reasons: no more special handling for
  168. first node pointers. Dummy tail nodes are also useful for the same reason:
  169. no more special handling for last node pointers.
  170. Having for the current node pointer an extra level of indirection -- by
  171. having it actually point to the preceding node -- isn't a necessity any
  172. more. The preceding node is now easily accessible. It still can have some
  173. advantages though: it does not have to be updated after creating a new
  174. node. But the extra level of indirection can be bothersome.
  175.  
  176.  
  177. === A.Reitsma, Delft, The Netherlands. 94-08-11 ====== Public Domain =====
  178.