Data Structures in C++
Public Member Functions | Protected Member Functions | Private Attributes
ProtectedLinkedList< T > Class Template Reference

Doubly-linked list implementation with dynamic memory allocation. More...

#include <ProtectedLinkedList.hpp>

Inheritance diagram for ProtectedLinkedList< T >:
Collaboration diagram for ProtectedLinkedList< T >:

Public Member Functions

string getName ()
 Provides the name of the data structure as a string representation. More...
 
 ProtectedLinkedList ()
 
 ~ProtectedLinkedList ()
 
int getSize ()
 Outputs the number of elements stored in the structure. More...
 
bool isEmpty ()
 Check whether the structure is empty. More...
 
bool isFull ()
 Check whether the structure is full. More...
 

Protected Member Functions

Node< T > * getNode (int index)
 
 ProtectedLinkedList (const T data[])
 create the structure and populate it with the data from the array More...
 
Node< T > * getFirst () const
 
Node< T > * getLast () const
 
virtual void insert (const T val)
 Insert an element at the end of the list. More...
 
virtual void insert (const T val, const int index)
 Insert an element at the specified position in the list. More...
 
virtual T remove (const int index)
 Remove an element from the list. More...
 
virtual T get (const int index)
 Get the element at the specified position in the list, without removing. More...
 
virtual Iterator< T > iterator ()
 Creates an Iterator, an object that allows the sequential access of values in a Linked List without the search overhead. More...
 

Private Attributes

Node< T > * first
 
Node< T > * last
 
int size = 0
 

Detailed Description

template<class T>
class ProtectedLinkedList< T >

Doubly-linked list implementation with dynamic memory allocation.

Many methods in this class are protected so the class can be used as an extension for other data structures.

Template Parameters
TThe type of object the data structure will contain

Definition at line 22 of file ProtectedLinkedList.hpp.

Constructor & Destructor Documentation

◆ ProtectedLinkedList() [1/2]

template<class T >
ProtectedLinkedList< T >::ProtectedLinkedList ( )
inline

Definition at line 35 of file ProtectedLinkedList.hpp.

35  {
36  first = last = NULL;
37  }

◆ ~ProtectedLinkedList()

template<class T >
ProtectedLinkedList< T >::~ProtectedLinkedList ( )
inline

Definition at line 39 of file ProtectedLinkedList.hpp.

39  {
40 
41  while (first != NULL) {
42  Node<T> *tmp = first;
43  first = first->getNext();
44  delete tmp;
45  }
46  last = NULL;
47  size = 0;
48  }
Node
Node used inside other data structures.
Definition: Node.hpp:15

◆ ProtectedLinkedList() [2/2]

template<class T >
ProtectedLinkedList< T >::ProtectedLinkedList ( const T  data[])
inlineexplicitprotected

create the structure and populate it with the data from the array

Parameters
dataan array with data with which the structure will be

Definition at line 73 of file ProtectedLinkedList.hpp.

73  {
74  for (int i = 0; i <= (sizeof(data) / sizeof(data[0])); i ++) {
75  insert(data[i]);
76  }
77  }
ProtectedLinkedList::insert
virtual void insert(const T val)
Insert an element at the end of the list.
Definition: ProtectedLinkedList.hpp:89

Member Function Documentation

◆ get()

template<class T >
virtual T ProtectedLinkedList< T >::get ( const int  index)
inlineprotectedvirtual

Get the element at the specified position in the list, without removing.

Parameters
indexindex of the desired element

Reimplemented in OrderedList< T >, and LinkedList< T >.

Definition at line 182 of file ProtectedLinkedList.hpp.

<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
182  {
183  if (index < 0) throw std::out_of_range("Negative index not allowed.");
184 
185  if (index > size) throw std::out_of_range("Nonexistent index.");
186 
187  Node<T> *tmp = getNode(index);
188  return tmp->getValue();
189  }
Node
Node used inside other data structures.
Definition: Node.hpp:15
=======
182  {
183  if (index < 0) throw out_of_range("Negative index not allowed.");
184 
185  if (index > size) throw out_of_range("Nonexistent index.");
186 
187  Node<T> *tmp = getNode(index);
188  return tmp->getValue();
189  }
Node
Node used inside other data structures.
Definition: Node.hpp:15
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
182  {
183  if (index < 0) throw out_of_range("Negative index not allowed.");
184 
185  if (index > size) throw out_of_range("Nonexistent index.");
186 
187  Node<T> *tmp = getNode(index);
188  return tmp->getValue();
189  }
Node
Node used inside other data structures.
Definition: Node.hpp:15
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
182  {
183  if (index < 0) throw out_of_range("Negative index not allowed.");
184 
185  if (index > size) throw out_of_range("Nonexistent index.");
186 
187  Node<T> *tmp = getNode(index);
188  return tmp->getValue();
189  }
Node
Node used inside other data structures.
Definition: Node.hpp:15
>>>>>>> master
ProtectedLinkedList::getNode
Node< T > * getNode(int index)
Definition: ProtectedLinkedList.hpp:52
Node::getValue
T getValue() const
Definition: Node.hpp:31
Here is the call graph for this function:

◆ getFirst()

template<class T >
Node<T>* ProtectedLinkedList< T >::getFirst ( ) const
inlineprotected

Definition at line 79 of file ProtectedLinkedList.hpp.

79  {
80  return first;
81  }

◆ getLast()

template<class T >
Node<T>* ProtectedLinkedList< T >::getLast ( ) const
inlineprotected

Definition at line 83 of file ProtectedLinkedList.hpp.

83  {
84  return last;
85  }

◆ getName()

template<class T >
string ProtectedLinkedList< T >::getName ( )
inlinevirtual

Provides the name of the data structure as a string representation.

Returns
name of the data structure

Implements DataStructure.

Reimplemented in LinkedList< T >, OrderedList< T >, and DynamicQueue< T >.

Definition at line 31 of file ProtectedLinkedList.hpp.

31  {
32  return "Protected Linked List";
33  }

◆ getNode()

template<class T >
Node<T>* ProtectedLinkedList< T >::getNode ( int  index)
inlineprotected

Definition at line 52 of file ProtectedLinkedList.hpp.

52  {
53  Node<T> *tmp;
54 
55  if (index <= size / 2) {
56  tmp = first;
57 
58  for (int i = 0; i < index; i ++)
59  tmp = tmp->getNext();
60  }
61  else {
62  tmp = last;
63 
64  for (int i = 0; i < size - index; i ++)
65  tmp = tmp->getPrevious();
66  }
67  return tmp;
68  }
Node
Node used inside other data structures.
Definition: Node.hpp:15
Node::getPrevious
Node * getPrevious() const
Definition: Node.hpp:47
Node::getNext
Node * getNext() const
Definition: Node.hpp:39
Here is the caller graph for this function:

◆ getSize()

template<class T >
int ProtectedLinkedList< T >::getSize ( )
inlinevirtual

Outputs the number of elements stored in the structure.

Returns
number of elements stored in the structure

Implements DataStructure.

Reimplemented in DynamicQueue< T >.

Definition at line 200 of file ProtectedLinkedList.hpp.

200  {
201  return size;
202  }
<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
Here is the call graph for this function:
=======
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
>>>>>>> master

◆ insert() [1/2]

template<class T >
virtual void ProtectedLinkedList< T >::insert ( const T  val)
inlineprotectedvirtual

Insert an element at the end of the list.

Parameters
valthe value to be inserted

Reimplemented in OrderedList< T >, and LinkedList< T >.

Definition at line 89 of file ProtectedLinkedList.hpp.

89  {
90  ProtectedLinkedList::insert(val, size);
91  }
ProtectedLinkedList::insert
virtual void insert(const T val)
Insert an element at the end of the list.
Definition: ProtectedLinkedList.hpp:89
<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
Here is the call graph for this function:
=======
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
>>>>>>> master

◆ insert() [2/2]

template<class T >
virtual void ProtectedLinkedList< T >::insert ( const T  val,
const int  index 
)
inlineprotectedvirtual

Insert an element at the specified position in the list.

Parameters
valthe value to be inserted
indexposition of the list that the element will be inserted on

Reimplemented in OrderedList< T >, and LinkedList< T >.

Definition at line 96 of file ProtectedLinkedList.hpp.

<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
96  {
97  if (index < 0) throw std::out_of_range("Negative index not allowed.");
98 
99  if (index > size) throw std::out_of_range("Nonexistent index.");
100 
101  // if it's the first element on the list, create the first node
102  if (size == 0) {
103  first = new Node<T>();
104  first->setValue(val);
105 
106  // first and last both point to the same node at the beginning
107  last = first;
108  }
109 
110  // if the insertion is at the beginning,
111  // use the pointer to the first node to
112  // speed things up and replace first too
113  else if (index == 0) {
114  first->setPrevious(new Node<T>());
115  first->getPrevious()->setNext(first);
116  first = first->getPrevious();
117  first->setValue(val);
118  }
119 
120  // the same applies when an insertion is made in the last node
121  // this is useful for the stack and queue implementations
122  else if (index == size) {
123  last->setNext(new Node<T>());
124  last->getNext()->setPrevious(last);
125  last = last->getNext();
126  last->setValue(val);
127  }
128 
129  // if the index is in the middle of the list, it must be traversed
130  else {
131  Node<T> *next = getNode(index);
132  Node<T> *previous = next->getPrevious();
133 
134  // a new node is created and put between
135  // the current node and the next one
136  Node<T> *middle = new Node<T>();
137  middle->setValue(val);
138 
139  middle->setNext(next);
140  next->setPrevious(middle);
141 
142  middle->setPrevious(previous);
143  previous->setNext(middle);
144  }
145  size ++;
146  }
=======
96  {
97  if (index < 0) throw out_of_range("Negative index not allowed.");
98 
99  if (index > size) throw out_of_range("Nonexistent index.");
100 
101  // if it's the first element on the list, create the first node
102  if (size == 0) {
103  first = new Node<T>();
104  first->setValue(val);
105 
106  // first and last both point to the same node at the beginning
107  last = first;
108  }
109 
110  // if the insertion is at the beginning,
111  // use the pointer to the first node to
112  // speed things up and replace first too
113  else if (index == 0) {
114  first->setPrevious(new Node<T>());
115  first->getPrevious()->setNext(first);
116  first = first->getPrevious();
117  first->setValue(val);
118  }
119 
120  // the same applies when an insertion is made in the last node
121  // this is useful for the stack and queue implementations
122  else if (index == size) {
123  last->setNext(new Node<T>());
124  last->getNext()->setPrevious(last);
125  last = last->getNext();
126  last->setValue(val);
127  }
128 
129  // if the index is in the middle of the list, it must be traversed
130  else {
131  Node<T> *next = getNode(index);
132  Node<T> *previous = next->getPrevious();
133 
134  // a new node is created and put between
135  // the current node and the next one
136  Node<T> *middle = new Node<T>();
137  middle->setValue(val);
138 
139  middle->setNext(next);
140  next->setPrevious(middle);
141 
142  middle->setPrevious(previous);
143  previous->setNext(middle);
144  }
145  size ++;
146  }
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
96  {
97  if (index < 0) throw out_of_range("Negative index not allowed.");
98 
99  if (index > size) throw out_of_range("Nonexistent index.");
100 
101  // if it's the first element on the list, create the first node
102  if (size == 0) {
103  first = new Node<T>();
104  first->setValue(val);
105 
106  // first and last both point to the same node at the beginning
107  last = first;
108  }
109 
110  // if the insertion is at the beginning,
111  // use the pointer to the first node to
112  // speed things up and replace first too
113  else if (index == 0) {
114  first->setPrevious(new Node<T>());
115  first->getPrevious()->setNext(first);
116  first = first->getPrevious();
117  first->setValue(val);
118  }
119 
120  // the same applies when an insertion is made in the last node
121  // this is useful for the stack and queue implementations
122  else if (index == size) {
123  last->setNext(new Node<T>());
124  last->getNext()->setPrevious(last);
125  last = last->getNext();
126  last->setValue(val);
127  }
128 
129  // if the index is in the middle of the list, it must be traversed
130  else {
131  Node<T> *next = getNode(index);
132  Node<T> *previous = next->getPrevious();
133 
134  // a new node is created and put between
135  // the current node and the next one
136  Node<T> *middle = new Node<T>();
137  middle->setValue(val);
138 
139  middle->setNext(next);
140  next->setPrevious(middle);
141 
142  middle->setPrevious(previous);
143  previous->setNext(middle);
144  }
145  size ++;
146  }
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
96  {
97  if (index < 0) throw out_of_range("Negative index not allowed.");
98 
99  if (index > size) throw out_of_range("Nonexistent index.");
100 
101  // if it's the first element on the list, create the first node
102  if (size == 0) {
103  first = new Node<T>();
104  first->setValue(val);
105 
106  // first and last both point to the same node at the beginning
107  last = first;
108  }
109 
110  // if the insertion is at the beginning,
111  // use the pointer to the first node to
112  // speed things up and replace first too
113  else if (index == 0) {
114  first->setPrevious(new Node<T>());
115  first->getPrevious()->setNext(first);
116  first = first->getPrevious();
117  first->setValue(val);
118  }
119 
120  // the same applies when an insertion is made in the last node
121  // this is useful for the stack and queue implementations
122  else if (index == size) {
123  last->setNext(new Node<T>());
124  last->getNext()->setPrevious(last);
125  last = last->getNext();
126  last->setValue(val);
127  }
128 
129  // if the index is in the middle of the list, it must be traversed
130  else {
131  Node<T> *next = getNode(index);
132  Node<T> *previous = next->getPrevious();
133 
134  // a new node is created and put between
135  // the current node and the next one
136  Node<T> *middle = new Node<T>();
137  middle->setValue(val);
138 
139  middle->setNext(next);
140  next->setPrevious(middle);
141 
142  middle->setPrevious(previous);
143  previous->setNext(middle);
144  }
145  size ++;
146  }
>>>>>>> master
Node
Node used inside other data structures.
Definition: Node.hpp:15
Node::setPrevious
void setPrevious(Node *previous)
Definition: Node.hpp:51
Node::setValue
void setValue(T value)
Definition: Node.hpp:35
Node::getPrevious
Node * getPrevious() const
Definition: Node.hpp:47
ProtectedLinkedList::getNode
Node< T > * getNode(int index)
Definition: ProtectedLinkedList.hpp:52
Node::setNext
void setNext(Node *next)
Definition: Node.hpp:43
Here is the call graph for this function:

◆ isEmpty()

template<class T >
bool ProtectedLinkedList< T >::isEmpty ( )
inlinevirtual

Check whether the structure is empty.

Returns
True if empty, otherwise false

Implements DataStructure.

Reimplemented in DynamicQueue< T >.

Definition at line 204 of file ProtectedLinkedList.hpp.

204  {
205  return size == 0;
206  }
<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
Here is the call graph for this function:
=======
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
>>>>>>> master

◆ isFull()

template<class T >
bool ProtectedLinkedList< T >::isFull ( )
inlinevirtual

Check whether the structure is full.

Returns
True if full, otherwise false

Implements DataStructure.

Reimplemented in DynamicQueue< T >.

Definition at line 208 of file ProtectedLinkedList.hpp.

<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
208  {
209  return false;
210  }
Here is the caller graph for this function:
=======
208  {
209  return false;
210  }
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
208  {
209  return false;
210  }
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
208  {
209  return false;
210  }
>>>>>>> master

◆ iterator()

template<class T >
virtual Iterator<T> ProtectedLinkedList< T >::iterator ( )
inlineprotectedvirtual

Creates an Iterator, an object that allows the sequential access of values in a Linked List without the search overhead.

Returns
an Iterator starting from the first node of the list

Reimplemented in LinkedList< T >.

Definition at line 194 of file ProtectedLinkedList.hpp.

<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
194  {
195  return Iterator<T>(first);
196  }
Iterator
Object that provides iterative powers to classes composed of Node.
Definition: Iterator.hpp:14
Here is the call graph for this function:
=======
194  {
195  return Iterator<T>(first);
196  }
Iterator
Object that provides iterative powers to classes composed of Node.
Definition: Iterator.hpp:13
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
194  {
195  return Iterator<T>(first);
196  }
Iterator
Object that provides iterative powers to classes composed of Node.
Definition: Iterator.hpp:13
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
194  {
195  return Iterator<T>(first);
196  }
Iterator
Object that provides iterative powers to classes composed of Node.
Definition: Iterator.hpp:13
>>>>>>> master

◆ remove()

template<class T >
virtual T ProtectedLinkedList< T >::remove ( const int  index)
inlineprotectedvirtual

Remove an element from the list.

Parameters
indexposition of the element to be removed
Returns
the element that is being removed

Reimplemented in OrderedList< T >, and LinkedList< T >.

Definition at line 151 of file ProtectedLinkedList.hpp.

<<<<<<< HEAD <<<<<<< HEAD <<<<<<< HEAD
151  {
152  if (index < 0) throw std::out_of_range("Negative index not allowed.");
153 
154  if (index >= size) throw std::out_of_range("Nonexistent index in list.");
155 
156  Node<T> *tmp = getNode(index);
157 
158  T ret = tmp->getValue();
159 
160  if (tmp->getPrevious() != NULL)
161  tmp->getPrevious()->setNext(tmp->getNext());
162  else
163  first = tmp->getNext();
164 
165  if (tmp->getNext() != NULL)
166  tmp->getNext()->setPrevious(tmp->getPrevious());
167  else
168  last = tmp->getPrevious();
169 
170  size --;
171 
172  tmp->setNext(NULL);
173  tmp->setPrevious(NULL);
174  delete tmp;
175 
176  return ret;
177  }
=======
151  {
152  if (index < 0) throw out_of_range("Negative index not allowed.");
153 
154  if (index >= size) throw out_of_range("Nonexistent index in list.");
155 
156  Node<T> *tmp = getNode(index);
157 
158  T ret = tmp->getValue();
159 
160  if (tmp->getPrevious() != NULL)
161  tmp->getPrevious()->setNext(tmp->getNext());
162  else
163  first = tmp->getNext();
164 
165  if (tmp->getNext() != NULL)
166  tmp->getNext()->setPrevious(tmp->getPrevious());
167  else
168  last = tmp->getPrevious();
169 
170  size --;
171 
172  tmp->setNext(NULL);
173  tmp->setPrevious(NULL);
174  delete tmp;
175 
176  return ret;
177  }
>>>>>>> 36f9b37... fixed dependency of ProtectedLinkedList to Iterator =======
151  {
152  if (index < 0) throw out_of_range("Negative index not allowed.");
153 
154  if (index >= size) throw out_of_range("Nonexistent index in list.");
155 
156  Node<T> *tmp = getNode(index);
157 
158  T ret = tmp->getValue();
159 
160  if (tmp->getPrevious() != NULL)
161  tmp->getPrevious()->setNext(tmp->getNext());
162  else
163  first = tmp->getNext();
164 
165  if (tmp->getNext() != NULL)
166  tmp->getNext()->setPrevious(tmp->getPrevious());
167  else
168  last = tmp->getPrevious();
169 
170  size --;
171 
172  tmp->setNext(NULL);
173  tmp->setPrevious(NULL);
174  delete tmp;
175 
176  return ret;
177  }
>>>>>>> bded2143692dca559ffcc9e7202d9eb5fbfc45bf =======
151  {
152  if (index < 0) throw out_of_range("Negative index not allowed.");
153 
154  if (index >= size) throw out_of_range("Nonexistent index in list.");
155 
156  Node<T> *tmp = getNode(index);
157 
158  T ret = tmp->getValue();
159 
160  if (tmp->getPrevious() != NULL)
161  tmp->getPrevious()->setNext(tmp->getNext());
162  else
163  first = tmp->getNext();
164 
165  if (tmp->getNext() != NULL)
166  tmp->getNext()->setPrevious(tmp->getPrevious());
167  else
168  last = tmp->getPrevious();
169 
170  size --;
171 
172  tmp->setNext(NULL);
173  tmp->setPrevious(NULL);
174  delete tmp;
175 
176  return ret;
177  }
>>>>>>> master
Node
Node used inside other data structures.
Definition: Node.hpp:15
Node::setPrevious
void setPrevious(Node *previous)
Definition: Node.hpp:51
Node::getPrevious
Node * getPrevious() const
Definition: Node.hpp:47
ProtectedLinkedList::getNode
Node< T > * getNode(int index)
Definition: ProtectedLinkedList.hpp:52
Node::setNext
void setNext(Node *next)
Definition: Node.hpp:43
Node::getValue
T getValue() const
Definition: Node.hpp:31
Node::getNext
Node * getNext() const
Definition: Node.hpp:39
Here is the call graph for this function:

Field Documentation

◆ first

template<class T >
Node<T>* ProtectedLinkedList< T >::first
private

Definition at line 25 of file ProtectedLinkedList.hpp.

◆ last

template<class T >
Node<T>* ProtectedLinkedList< T >::last
private

Definition at line 26 of file ProtectedLinkedList.hpp.

◆ size

template<class T >
int ProtectedLinkedList< T >::size = 0
private

Definition at line 27 of file ProtectedLinkedList.hpp.

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.13