1 #ifndef SINGLY_LINKED_LIST_CLASS
2 #define SINGLY_LINKED_LIST_CLASS
5 * Name : singly_linked_list
6 * Author : Chris Koeritz
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
19 //class node; // forward.
21 //! Implements a singly-linked list structure.
23 class singly_linked_list : public node
26 singly_linked_list() : node(1) {}
28 //hmmm: clean up all children?
29 ~singly_linked_list() {}
31 // symbol for the rest of the list linked here.
32 static const int NEXT_NODE = 0;
35 //!< returns the number of items currently in the list, including this node.
36 /*!< this is a costly operation. */
38 singly_linked_list *next() { return (singly_linked_list *)get_link(NEXT_NODE); }
40 void set_next(singly_linked_list *new_next) { set_link(NEXT_NODE, new_next); }
42 //! returns true if this list has a cycle in it.
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.
50 if (b != NULL_POINTER) b = b->next();
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.
58 // if we fell out of the list iteration with a null for either pointer,
59 // then there was no cycle in the list.
65 singly_linked_list(const singly_linked_list &);
66 singly_linked_list &operator =(const singly_linked_list &);