-
Notifications
You must be signed in to change notification settings - Fork 1
/
linkedlist.h
79 lines (64 loc) · 1.91 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
// Copyright 2021 András Mihálykó MIT License
#pragma once
/*
Doubly linked list template . Used for its capability
of deleting items in O(1) running time.
*/
template<typename T>class Node{
private:
T data;
Node<T>* prev;
Node<T>* next;
public:
Node() {}
Node<T>* getNext() {return next;}
Node<T>* getPrevious() {return prev;}
void setNext(Node<T>* next_) {next = next_;}
void setPrevious(Node<T> * prev_) {prev = prev_;}
void setData(T data_) {data = data_;}
T getData() const {return data;}
void setNode(T data_) {data = data_;}
};
template<typename T>class List{
private:
Node<T>* first;
int numbOfData;
public:
List() {first = NULL; numbOfData = 0;}
~List() {
Node<T>* next;
while (first != NULL) {
next = first->getNext();
delete first;
first = next;
}
}
void push_front(T new_data);
void deleteNode(Node<T>* nodeToDelete);
bool isEmpty() const {return numbOfData == 0;}
Node<T>* getFirst() {return first;}
};
template<typename T> void List<T>::push_front(T new_data) {
Node<T>* new_node = new Node<T>();
new_node->setData(new_data);
new_node->setPrevious(NULL);
new_node->setNext(first);
if (first != NULL)
first->setPrevious(new_node);
first = new_node;
numbOfData++;
}
template<typename T> void List<T>::deleteNode(Node<T>* nodeToDelete) {
if (nodeToDelete == NULL)
return;
if (nodeToDelete == first) { // delete the first
first = nodeToDelete->getNext();
}
if (nodeToDelete->getNext() != NULL)
nodeToDelete->getNext()->setPrevious(nodeToDelete->getPrevious());
// Change prev only if node to be deleted is NOT the first node
if (nodeToDelete->getPrevious() != NULL)
nodeToDelete->getPrevious()->setNext(nodeToDelete->getNext());
delete nodeToDelete;
numbOfData--;
}