data_structures::linked_list::list Class Reference

Collaboration diagram for data_structures::linked_list::list:

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 68 of file reverse_a_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.

           {
        // Initialize the first link
        first = std::make_shared<link>();
        // Initialize the last link with the first link
        last = nullptr;
    }

~list()

list::~list

(

)

Definition at line 196 of file reverse_a_linked_list.cpp.

{ delete_all_nodes(); }

list() [2/2]

data_structures::linked_list::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.

{ 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.

                                                     {
    assert(isEmpty());
    head = copy_all_nodes(other.head);
}

delete_all_nodes()

void data_structures::linked_list::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.

                            {
    while (head != nullptr) {
        const auto tmp_node = head->next;
        delete head;
        head = tmp_node;
    }
}

display()

void data_structures::linked_list::list::display

(

)

function displays all the elements in the list

Returns

'void'

Definition at line 181 of file linked_list.cpp.

                   {
    if (isEmpty()) {
        std::cout << "List is Empty!";
        return;
    }
    std::shared_ptr<link> t = first;
    while (t->succ() != nullptr) {
        std::cout << t->succ()->val() << "\t";
        t = t->succ();
    }
}

erase()

void data_structures::linked_list::list::erase

(

int

old_elem

)

function erases old element from the list

Parameters

old_elem

to be erased from the list

Definition at line 152 of file linked_list.cpp.

                             {
    if (isEmpty()) {
        std::cout << "List is Empty!";
        return;
    }
    std::shared_ptr<link> t = first;
    std::shared_ptr<link> to_be_removed = nullptr;
    while (t != last && t->succ()->val() != old_elem) {
        t = t->succ();
    }
    if (t == last) {
        std::cout << "Element not found\n";
        return;
    }
    to_be_removed = t->succ();
    t->succ() = t->succ()->succ();
    to_be_removed.reset();
    if (t->succ() == nullptr) {
        last = t;
    }
    if (first == last){
        last = nullptr;
    }
}

insert()

void data_structures::linked_list::list::insert

(

int32_t

n

)

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

Parameters

new_elem

element be added at the end of the list

Definition at line 99 of file reverse_a_linked_list.cpp.

                           {
    try {
        // NOLINTNEXTLINE(cppcoreguidelines-owning-memory)
        Node* new_node = new Node();
        Node* temp = nullptr;
        new_node->val = n;
        new_node->next = nullptr;
        if (isEmpty()) {
            head = new_node;
        } else {
            temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = new_node;
        }
    } catch (std::bad_alloc& exception) {
        std::cerr << "bad_alloc detected: " << exception.what() << "\n";
    }
}

isEmpty() [1/2]

bool data_structures::linked_list::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.

                   {
    if (last == nullptr) {
        return true;
    } else {
        return false;
    }
}

isEmpty() [2/2]

bool data_structures::linked_list::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.

{ return head == nullptr; }

operator=()

list & data_structures::linked_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.

                                       {
    if (this == &other) {
        return *this;
    }
    delete_all_nodes();
 
    copy_all_nodes_from_list(other);
    return *this;
}

push_back()

void data_structures::linked_list::list::push_back

(

int

new_elem

)

function adds new element to the end of the list

Parameters

new_elem

to be added to the end of the list

Definition at line 123 of file linked_list.cpp.

                                 {
    if (isEmpty()) {
        first->succ() = std::make_shared<link>(new_elem);
        last = first->succ();
    } else {
        last->succ() = std::make_shared<link>(new_elem);
        last = last->succ();
    }
}

push_front()

void data_structures::linked_list::list::push_front

(

int

new_elem

)

function adds new element to the beginning of the list

Parameters

new_elem

to be added to front of the list

Definition at line 137 of file linked_list.cpp.

                                  {
    if (isEmpty()) {
        first->succ() = std::make_shared<link>(new_elem);
        last = first->succ();
    } else {
        std::shared_ptr<link> t = std::make_shared<link>(new_elem);
        t->succ() = first->succ();
        first->succ() = t;
    }
}

reverseList()

void data_structures::linked_list::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.

                       {
    Node* curr = head;
    Node* prev = nullptr;
    Node* next_node = nullptr;
    while (curr != nullptr) {
        next_node = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next_node;
    }
    head = prev;
}

search()

std::shared_ptr< link > data_structures::linked_list::list::search

(

int

find_elem

)

function searchs for

Parameters

find_elem	in the list
find_elem	to be searched for in the list

Definition at line 197 of file linked_list.cpp.

                                              {
    if (isEmpty()) {
        std::cout << "List is Empty!";
        return nullptr;
    }
    std::shared_ptr<link> t = first;
    while (t != last && t->succ()->val() != find_elem) {
        t = t->succ();
    }
    if (t == last) {
        std::cout << "Element not found\n";
        return nullptr;
    }
    std::cout << "Element was found\n";
    return t->succ();
}

top()

int32_t data_structures::linked_list::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.

                        {
    if (!isEmpty()) {
        return head->val;
    } else {
        throw std::logic_error("List is empty");
    }
}

traverse()

int32_t data_structures::linked_list::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.

                                          {
    Node* current = head;
 
    int count = 0;
    while (current != nullptr) {
        if (count == index) {
            return (current->val);
        }
        count++;
        current = current->next;
    }
 
    /* if we get to this line,the caller was asking for a non-existent element
    so we assert fail */
    exit(1);
}

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 data_structures::linked_list::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:

• data_structures/linked_list.cpp
• data_structures/reverse_a_linked_list.cpp