Concept of an Element (Node)

From

(Difference between revisions)
Jump to: navigation, search
(Examples of Abstract Node Implementation)
(Examples of Abstract Node Implementation)
 
(6 intermediate revisions not shown)
Line 1: Line 1:
-
A '''node''' is an abstract basic unit used to build linked [[data structure]]s such as [[tree data structure|trees]], [[linked list]]s, and computer-based representations of [[graph (data structure)|graphs]]. Each node contains some [[data]] and possibly links to other nodes. Links between nodes are often implemented by [[Data pointer|pointer]]s or [[Reference (computer science)|reference]]s.
+
<noinclude>
 +
{{CS2:BookNav|base=/|up=Contents: CS2|prev=Primitive and Composite Structures|next=Abstract Data Types}}
 +
</noinclude>
 +
<br/>
-
A node can be thought of as a logical placeholder for some data. It is a memory block which contains some data unit and perhaps references to other nodes, which in turn contain data and perhaps references to yet more nodes. By forming chains of interlinked nodes, very large and complex data structures can be formed.
+
A '''node''' is an abstract basic unit used to build linked data structures such as linked lists, trees, and graphs. Each node contains some data and possibly links to other nodes. Links between nodes are often implemented by pointers or references.
 +
<br/><br/>
-
Nodes are conceptually similar to [[vertex (graph theory)|vertices]], which are elements of a [[Graph (mathematics)|graph]].
+
A node can be thought of as a logical placeholder for some data. It is a memory block which contains some data unit and perhaps references to other nodes, which in turn contain data and perhaps references to yet more nodes. By forming chains of interlinked nodes, very large and complex data structures can be formed.
 +
<br/><br/>
== Examples of Abstract Node Implementation ==
== Examples of Abstract Node Implementation ==
Line 11: Line 16:
   '''class''' ''Node'' {
   '''class''' ''Node'' {
     data ''// The data being stored in the node''
     data ''// The data being stored in the node''
-
     next ''// A [[Reference (computer science)|reference]] to the next node, null if last node''
+
     next ''// A reference to the next node, null if last node''
   }
   }
Here three such nodes form a singly-linked list of length 3.
Here three such nodes form a singly-linked list of length 3.
-
<br>[[Image:Singly_linked_list_delete_after.png]]
+
<br>[[Image:Singly-linked-list.svg]]
<br>
<br>
Line 24: Line 29:
   '''class''' ''Node'' {
   '''class''' ''Node'' {
     data ''// The data being stored in the node''
     data ''// The data being stored in the node''
-
     previous ''// A [[Reference (computer science)|reference]] to the previous node, null if first node''
+
     previous ''// A reference to the previous node, null if first node''
-
     next ''// A [[Reference (computer science)|reference]] to the next node, null if last node''
+
     next ''// A reference to the next node, null if last node''
   }
   }
-
Here two such nodes form a doubly-linked list of length 2.
+
Here three such nodes form a doubly-linked list of length 3.
-
[[Image:]]
 
-
<br>
 
-
<br>(...Java Example Link...)
+
&nbsp;&nbsp;&nbsp; [[Image:Doubly-linked-list.svg]]
-
 
+
-
(...C++ Example Link...)&nbsp;
+
-
 
+
-
<br>
+
-
<br>[[CS2|Back to Data Structures (CS2)]]
 
-
[[Category:Linked_lists]] [[Category:Trees_(structure)]] [[Category:Graph_data_structures]]
+
----
 +
{{CS2/ChapNav}}
 +
----
 +
[[Category:CS2|{{SUBPAGENAME}}]]

Current revision as of 22:16, 9 April 2009

← Primitive and Composite Structures ↑ Contents: CS2 Abstract Data Types →


A node is an abstract basic unit used to build linked data structures such as linked lists, trees, and graphs. Each node contains some data and possibly links to other nodes. Links between nodes are often implemented by pointers or references.

A node can be thought of as a logical placeholder for some data. It is a memory block which contains some data unit and perhaps references to other nodes, which in turn contain data and perhaps references to yet more nodes. By forming chains of interlinked nodes, very large and complex data structures can be formed.

Examples of Abstract Node Implementation

A node containing a single reference field.

 class Node {
    data // The data being stored in the node
    next // A reference to the next node, null if last node
 }

Here three such nodes form a singly-linked list of length 3.


Image:Singly-linked-list.svg


A node containing two reference fields.

 class Node {
    data // The data being stored in the node
    previous // A reference to the previous node, null if first node
    next // A reference to the next node, null if last node
 }

Here three such nodes form a doubly-linked list of length 3.


    Image:Doubly-linked-list.svg



CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs


Personal tools
MediaWiki Appliance - Powered by TurnKey Linux