TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
data_structures::linked_list::list Class Reference
Collaboration diagram for data_structures::linked_list::list:
[legend]

Public Member Functions

 list ()
bool isEmpty ()
void push_back (int new_elem)
void push_front (int new_elem)
void erase (int old_elem)
void display ()
std::shared_ptr< link > search (int find_elem)
void reverse ()
bool isEmpty () const
 Utility function that checks if the list is empty.
void insert (int32_t new_elem)
 Utility function that adds a new element at the end of the list.
void reverseList ()
 Utility function for reversing a list.
void display () const
int32_t top () const
 Utility function to find the top element of the list.
int32_t last () const
int32_t traverse (int32_t index) const
 Utility function to find the i th element of the list.
 list (const list &other)
 copy constructor creating a deep copy of every node of the input
list & operator= (const list &other)
 assignment operator creating a deep copy of every node of the input

Private Member Functions

void delete_all_nodes ()
 calls delete operator on every node in the represented list
void copy_all_nodes_from_list (const list &other)

Private Attributes

std::shared_ptr< link > first
 link before the actual first element
std::shared_ptr< link > last
 last link on the list
Node * head = nullptr

Detailed Description

A list class containing a sequence of links

Definition at line 81 of file linked_list.cpp.

Constructor & Destructor Documentation

◆ list() [1/2]

data_structures::linked_list::list::list ( )
inline

List constructor. Initializes the first and last link.

Definition at line 89 of file linked_list.cpp.

89 {
90 // Initialize the first link
91 first = std::make_shared<link>();
92 // Initialize the last link with the first link
93 last = nullptr;
94 }
data_structures::linked_list::list::first
std::shared_ptr< link > first
link before the actual first element
Definition linked_list.cpp:83
data_structures::linked_list::list::last
std::shared_ptr< link > last
last link on the list
Definition linked_list.cpp:84

◆ ~list()

list::~list ( )

Definition at line 196 of file reverse_a_linked_list.cpp.

196{ delete_all_nodes(); }
data_structures::linked_list::list::delete_all_nodes
void delete_all_nodes()
calls delete operator on every node in the represented list
Definition reverse_a_linked_list.cpp:188

◆ list() [2/2]

list::list ( const list & other)

copy constructor creating a deep copy of every node of the input

Definition at line 206 of file reverse_a_linked_list.cpp.

206{ copy_all_nodes_from_list(other); }

Member Function Documentation

◆ copy_all_nodes_from_list()

void list::copy_all_nodes_from_list ( const list & other)
private

Definition at line 198 of file reverse_a_linked_list.cpp.

198 {
199 assert(isEmpty());
200 head = copy_all_nodes(other.head);
201}
data_structures::linked_list::list::isEmpty
bool isEmpty()
Definition linked_list.cpp:111
data_structures::linked_list::copy_all_nodes
Node * copy_all_nodes(const Node *const node)
creates a deep copy of a list starting at the input node
Definition reverse_a_linked_list.cpp:53

◆ delete_all_nodes()

void list::delete_all_nodes ( )
private

calls delete operator on every node in the represented list

Definition at line 188 of file reverse_a_linked_list.cpp.

188 {
189 while (head != nullptr) {
190 const auto tmp_node = head->next;
191 delete head;
192 head = tmp_node;
193 }
194}

◆ display()

void list::display ( )

function displays all the elements in the list

Returns
'void'

Definition at line 181 of file linked_list.cpp.

181 {
182 if (isEmpty()) {
183 std::cout << "List is Empty!";
184 return;
185 }
186 std::shared_ptr<link> t = first;
187 while (t->succ() != nullptr) {
188 std::cout << t->succ()->val() << "\t";
189 t = t->succ();
190 }
191}

◆ erase()

void list::erase ( int old_elem)

function erases old element from the list

Parameters
old_elemto be erased from the list

Definition at line 152 of file linked_list.cpp.

152 {
153 if (isEmpty()) {
154 std::cout << "List is Empty!";
155 return;
156 }
157 std::shared_ptr<link> t = first;
158 std::shared_ptr<link> to_be_removed = nullptr;
159 while (t != last && t->succ()->val() != old_elem) {
160 t = t->succ();
161 }
162 if (t == last) {
163 std::cout << "Element not found\n";
164 return;
165 }
166 to_be_removed = t->succ();
167 t->succ() = t->succ()->succ();
168 to_be_removed.reset();
169 if (t->succ() == nullptr) {
170 last = t;
171 }
172 if (first == last){
173 last = nullptr;
174 }
175}

◆ insert()

void list::insert ( int32_t n)

Utility function that adds a new element at the end of the list.

Parameters
new_elemelement be added at the end of the list

Definition at line 99 of file reverse_a_linked_list.cpp.

99 {
100 try {
101 // NOLINTNEXTLINE(cppcoreguidelines-owning-memory)
102 Node* new_node = new Node();
103 Node* temp = nullptr;
104 new_node->val = n;
105 new_node->next = nullptr;
106 if (isEmpty()) {
107 head = new_node;
108 } else {
109 temp = head;
110 while (temp->next != nullptr) {
111 temp = temp->next;
112 }
113 temp->next = new_node;
114 }
115 } catch (std::bad_alloc& exception) {
116 std::cerr << "bad_alloc detected: " << exception.what() << "\n";
117 }
118}

◆ isEmpty() [1/2]

bool list::isEmpty ( )

function checks if list is empty

Returns
true if list is empty
false if list is not empty

Definition at line 111 of file linked_list.cpp.

111 {
112 if (last == nullptr) {
113 return true;
114 } else {
115 return false;
116 }
117}

◆ isEmpty() [2/2]

bool list::isEmpty ( ) const

Utility function that checks if the list is empty.

Returns
true if the list is empty
false if the list is not empty

Definition at line 93 of file reverse_a_linked_list.cpp.

93{ return head == nullptr; }

◆ operator=()

list & list::operator= ( const list & other)

assignment operator creating a deep copy of every node of the input

Definition at line 211 of file reverse_a_linked_list.cpp.

211 {
212 if (this == &other) {
213 return *this;
214 }
215 delete_all_nodes();
216
217 copy_all_nodes_from_list(other);
218 return *this;
219}

◆ push_back()

void list::push_back ( int new_elem)

function adds new element to the end of the list

Parameters
new_elemto be added to the end of the list

Definition at line 123 of file linked_list.cpp.

123 {
124 if (isEmpty()) {
125 first->succ() = std::make_shared<link>(new_elem);
126 last = first->succ();
127 } else {
128 last->succ() = std::make_shared<link>(new_elem);
129 last = last->succ();
130 }
131}

◆ push_front()

void list::push_front ( int new_elem)

function adds new element to the beginning of the list

Parameters
new_elemto be added to front of the list

Definition at line 137 of file linked_list.cpp.

137 {
138 if (isEmpty()) {
139 first->succ() = std::make_shared<link>(new_elem);
140 last = first->succ();
141 } else {
142 std::shared_ptr<link> t = std::make_shared<link>(new_elem);
143 t->succ() = first->succ();
144 first->succ() = t;
145 }
146}

◆ reverseList()

void list::reverseList ( )

Utility function for reversing a list.

Using the current, previous, and next pointer.

Returns
void

Definition at line 125 of file reverse_a_linked_list.cpp.

125 {
126 Node* curr = head;
127 Node* prev = nullptr;
128 Node* next_node = nullptr;
129 while (curr != nullptr) {
130 next_node = curr->next;
131 curr->next = prev;
132 prev = curr;
133 curr = next_node;
134 }
135 head = prev;
136}

◆ search()

std::shared_ptr< link > list::search ( int find_elem)

function searchs for

Parameters
find_elemin the list
find_elemto be searched for in the list

Definition at line 197 of file linked_list.cpp.

197 {
198 if (isEmpty()) {
199 std::cout << "List is Empty!";
200 return nullptr;
201 }
202 std::shared_ptr<link> t = first;
203 while (t != last && t->succ()->val() != find_elem) {
204 t = t->succ();
205 }
206 if (t == last) {
207 std::cout << "Element not found\n";
208 return nullptr;
209 }
210 std::cout << "Element was found\n";
211 return t->succ();
212}

◆ top()

int32_t list::top ( ) const

Utility function to find the top element of the list.

Returns
the top element of the list

Definition at line 142 of file reverse_a_linked_list.cpp.

142 {
143 if (!isEmpty()) {
144 return head->val;
145 } else {
146 throw std::logic_error("List is empty");
147 }
148}

◆ traverse()

int32_t list::traverse ( int32_t index) const

Utility function to find the i th element of the list.

Returns
the i th element of the list

Definition at line 168 of file reverse_a_linked_list.cpp.

168 {
169 Node* current = head;
170
171 int count = 0;
172 while (current != nullptr) {
173 if (count == index) {
174 return (current->val);
175 }
176 count++;
177 current = current->next;
178 }
179
180 /* if we get to this line,the caller was asking for a non-existent element
181 so we assert fail */
182 exit(1);
183}

Member Data Documentation

◆ first

std::shared_ptr<link> data_structures::linked_list::list::first
private

link before the actual first element

Definition at line 83 of file linked_list.cpp.

◆ head

Node* data_structures::linked_list::list::head = nullptr
private

Definition at line 70 of file reverse_a_linked_list.cpp.

◆ last

int32_t list::last
private

last link on the list

Utility function to find the last element of the list.

Returns
the last element of the list

Definition at line 84 of file linked_list.cpp.

The documentation for this class was generated from the following files: