File: l_sllist.h

package info (click to toggle)
acs 021-2.3
  • links: PTS
  • area: main
  • in suites: slink
  • size: 2,196 kB
  • ctags: 2,629
  • sloc: cpp: 15,013; makefile: 166
file content (87 lines) | stat: -rw-r--r-- 2,507 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
  Philip White, mod by Al Davis
  list.h
  class example
  This is the header for the list class.  The list class is a singularly
  linked list with a dummy head and tail node.  The nodes of this list
  are of type "node" which is a struct that contains an element of type
  "list_element" (which in this example is an integer) and a next
  pointer which is used to link the list together.
*/
#ifndef ListH
#define ListH

// list_element is the type of data in a node of the linked list

typedef int list_element;

// DUMMY is a constant that is filled in for the dummy head and tail
// nodes

const list_element DUMMY=-9999;

// The node is the object that will be linked together in the list

struct node
{
  list_element data;
  node * next;
};

/* 
   The list is the class that builds the linked list out of nodes
   It provides 3 pointers, 
   - head which points to the dummy head node
   - tail which points to the dummy tail node
   - curr which is a temporary pointer that is moved up and down the
     list.  The curr pointer is moved directly by the first and next
     functions, and indirectly by the find and find_prior functions.
   NOTE the curr pointer should never be NULL, since we don't ever check
        for NULL.  Instead we always re-set curr with first();
 	(curr=head->next;) whenever we lose our current curr.
*/

class list
{
private:
  node * head, * tail, * curr;

  node * create_node(list_element e);	// creates a new node from an element
  void init_empty();			// build empty list
public:
  list() {init_empty();}
  list(list_element e) {init_empty(); add_front(e);}
  list(list &l) {init_empty(); copy(l);}
  ~list();

  void add_front(list_element x); // add to list 
  void add_sort(list_element x);
  void add_curr(list_element x);
  void add_tail(list_element x);

  void next(){curr=curr->next;}
  void first(){curr=head->next;}
  int find(list_element);	  // find matching element
  int find_prior(list_element);	  // find el. in front of matching el.
  void copy(list &l);		  // make self become a copy of l

  // returns the element at the curr location
  list_element get_data()
    {
      if (curr!=NULL)
        return curr->data;
      else
	return DUMMY;
    }

  int is_empty(){return (head->next == tail);}  // questions
  int is_last(){return (curr->next==tail);}
  int is_first(){return (curr==head->next);}

  void delete_curr();		// remove current element
  void clear();			// remove everything

  void print();			// print out whole list
};

#endif