feisty meow concerns codebase  2.140
singly_linked_list.h
Go to the documentation of this file.
1 #ifndef SINGLY_LINKED_LIST_CLASS
2 #define SINGLY_LINKED_LIST_CLASS
3 
4 /*
5 * Name : singly_linked_list
6 * Author : Chris Koeritz
7 **
8 * Copyright (c) 1998-$now By Author. This program is free software; you can
9 * redistribute it and/or modify it under the terms of the GNU General Public
10 * License as published by the Free Software Foundation; either version 2 of
11 * the License or (at your option) any later version. This is online at:
12 * http://www.fsf.org/copyleft/gpl.html
13 * Please send any updates to: fred@gruntose.com
14 */
15 #include "node.h"
16 
17 namespace nodes {
18 
19 //class node; // forward.
20 
22 
23 class singly_linked_list : public node
24 {
25 public:
27 
28  //hmmm: clean up all children?
30 
31  // symbol for the rest of the list linked here.
32  static const int NEXT_NODE = 0;
33 
34  int elements() const;
36 
39 
40  void set_next(singly_linked_list *new_next) { set_link(NEXT_NODE, new_next); }
41 
43  static bool has_cycle(singly_linked_list *check) {
44  singly_linked_list *a = check;
45  singly_linked_list *b = check;
46  while ((a != NULL_POINTER) && (b!= NULL_POINTER) ) {
47  a = a->next(); // move position of a forward once.
48  // move position of b forward twice.
49  b = b->next();
50  if (b != NULL_POINTER) b = b->next();
51 
52  if (a == b) {
53  // argh, our single skipper and double skipper have arrived at the same node.
54  // the only way that can happen is if there's a cycle in the list.
55  return true;
56  }
57  }
58  // if we fell out of the list iteration with a null for either pointer,
59  // then there was no cycle in the list.
60  return false;
61  }
62 
63 private:
64  // not permitted.
66  singly_linked_list &operator =(const singly_linked_list &);
67 };
68 
69 } // namespace.
70 
71 #endif
72 
An object representing the interstitial cell in most linked data structures.
Definition: node.h:41
void set_link(int link_number, node *new_link)
Connects the node "new_link" to this node.
Definition: node.cpp:62
node * get_link(int link_number) const
Returns the node that is connected to the specified "link_number".
Definition: node.cpp:85
Implements a singly-linked list structure.
static bool has_cycle(singly_linked_list *check)
returns true if this list has a cycle in it.
int elements() const
returns the number of items currently in the list, including this node.
singly_linked_list * next()
void set_next(singly_linked_list *new_next)
#define NULL_POINTER
The value representing a pointer to nothing.
Definition: definitions.h:32