DataStructures/LinkedList.cpp at master · TheRNB/DataStructures · GitHub

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <cstddef>
#include <iostream>
#include <stdexcept>

template <typename DataType>
class Node {
public:
	Node(DataType startingValue) {
		next = NULL;
		value = startingValue;
	}
	void setValue (DataType newValue) {
		value = newValue;
		;
	}
	void setNext (Node<DataType>* newNext) {
		next = newNext;
		;
	}
	DataType getValue() {
		return value;
		;
	}
	Node<DataType>* getNext() {
		return next;
		;
	}
	void operator= (const Node<DataType> &assignee) {
		value = assignee->getValue();
		;
	}
private:
	Node<DataType>* next;
	DataType value;
};

template <typename DataType>
class LinkedList {
public:
	LinkedList() {
		beginn = NULL;
		endd = NULL;
		sizee = 0;
	}
	Node<DataType> &operator[] (int index) {
		if (index >= sizee)
			throw std::invalid_argument("index out of bound");

		Node<DataType>* currVertex = beginn;
		while (0 < index) {
			currVertex = currVertex->getNext();
			index--;
		}
		return currVertex;
	}
	void push_back(DataType newNodeValue) {
		Node<DataType>* newNode = new Node<DataType>(newNodeValue);
		if (endd == NULL) {
			beginn = endd = newNode;
		} else {
			endd->setNext(newNode);
			endd = newNode;
		}
		sizee++;
	}
	void push_front(DataType newNodeValue) {
		Node<DataType>* newNode = new Node<DataType>(newNodeValue);
		if (beginn == NULL) {
			beginn = endd = newNode;
		} else {
			newNode->setNext(beginn);
			beginn = newNode;
		}
		sizee++;
	}
	DataType pop_back() {
		Node<DataType> *previousVertex = NULL;
		Node<DataType> *currVertex = beginn;
		if (currVertex == NULL)
			throw std::invalid_argument("list is empty");
		while (currVertex->getNext() != NULL) {
			previousVertex = currVertex;
			currVertex = currVertex->getNext();
		}
		if (endd == beginn) {
			beginn = NULL;
		}
		endd = previousVertex;
		sizee--;
		DataType returnValue = currVertex->getValue();
		delete currVertex;
		return returnValue;
	}
	DataType pop_front() {
		Node<DataType>* result = beginn;
		if (result == NULL)
			throw std::invalid_argument("list is empty");
		if (endd == beginn) {
			endd = NULL;
		}
		beginn = beginn->getNext();
		sizee--;
		DataType returnValue = result->getValue();
		delete result;
		return returnValue;
	}
	Node<DataType>* begin() {
		return beginn;
		;
	}
	Node<DataType>* end() {
		return endd;
		;
	}
	bool isEmpty() {
		return ((sizee==0)?true:false);
		;
	}
	int size() {
		return sizee;
		;
	}
	void operator= (const LinkedList<DataType> &assignee) {
		Node<DataType>* assigneeNode = assignee.begin();
		while (assigneeNode->getNext() != NULL) {
			if (beginn == NULL) {
				Node<DataType> newNode = new Node<DataType>(assigneeNode->getValue());
				beginn = endd = newNode;
			} else {
				Node<DataType> newNode = new Node<DataType>(assigneeNode->getValue());
				endd->setNext(newNode);
				endd = newNode;
			}
			assigneeNode = assigneeNode->getNext();
		}
		sizee = assignee.size();
	}
private:
	Node<DataType>* beginn;
	Node<DataType>* endd;
	int sizee;
};