This repository has been archived by the owner on Nov 16, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedList.h
154 lines (122 loc) · 3.5 KB
/
LinkedList.h
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
143
144
145
146
147
148
149
150
151
152
153
154
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"
#include <stdexcept>
template <typename T>
class LinkedList {
Node<T> *head;
int len;
Node<T>* getNode(int index) {
Node<T> *n = head;
for (int i = 0; i < index; i++, n = n->next);
return n;
};
public:
// default constructor - creates an empty list
LinkedList(): head(nullptr), len(0) {};
// copy constructor
LinkedList(const LinkedList<T>& other): len(other.len) {
if (other.head == nullptr) {
head = nullptr;
return;
}
head = new Node<T>(other.head->value);
Node<T> *n = head;
Node<T> *next = other.head->next;
while (next != nullptr) {
n->next = new Node<T>(next->value);
n = n->next;
next = next->next;
}
};
// move constructor
LinkedList(LinkedList<T>&& other): LinkedList() {
swap(*this, other);
};
~LinkedList() {
for (Node<T> *n = head; n != nullptr;) {
Node<T> *old = n;
n = n->next;
delete old;
}
};
// assignment operator - copies or moves value on right side depending if
// it's an l- or r-value
LinkedList<T>& operator=(LinkedList<T> other) {
swap(*this, other);
return *this;
};
// adds a value to the end of the list
void add(const T& value) {
if (head == nullptr) {
head = new Node<T>(value);
} else {
getNode(len - 1)->next = new Node<T>(value);
}
len++;
};
// adds a value at the specified index, shifting everything at index or
// greater up by one index
void add(int index, const T& value) {
if (index < 0 || index > len) {
throw std::out_of_range("index out of range");
}
if (index == len) {
return add(value);
}
Node<T> *newN = new Node<T>(value);
if (index == 0) {
newN->next = head;
head = newN;
} else {
Node<T> *previous = getNode(index - 1);
newN->next = previous->next;
previous->next = newN;
}
len++;
};
// retreives the value at an index
T get(int index) {
if (index < 0 || index >= len) {
throw std::out_of_range("index out of range");
}
Node<T> *n = getNode(index);
return n->value;
};
int length() {
return len;
}
// removes the value at an index, shifting everything at index or greater
// down by one index
void remove(int index) {
if (index < 0 || index >= len) {
throw std::out_of_range("index out of range");
}
Node<T> *old;
if (index == 0) {
old = head;
head = head->next;
} else {
Node<T> *previous = getNode(index - 1);
old = previous->next;
previous->next = old->next;
}
delete old;
len--;
};
// sets the value at an index
void set(int index, const T& value) {
if (index < 0 || index >= len) {
throw std::out_of_range("index out of range");
}
Node<T> *n = getNode(index);
n->value = value;
};
friend void swap(LinkedList<T>& first, LinkedList<T>& second) {
using std::swap; //enable ADL
swap(first.head, second.head);
swap(first.len, second.len);
};
// TODO: add iterator
};
#endif // LINKEDLIST_H