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

Constructor & Destructor Documentation

list() [1/2]

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

inline

List constructor. Initializes the first and last link.

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

~list()

list::~list

(

)

{ delete_all_nodes(); }

list() [2/2]

list::list

(

const list &

other

)

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

{ 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

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

delete_all_nodes()

void list::delete_all_nodes ( )

private

calls delete operator on every node in the represented list

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

display()

void list::display

(

)

function displays all the elements in the list

Returns

'void'

                   {
    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();
    }
}

Here is the call graph for this function:

erase()

void list::erase

(

int

old_elem

)

function erases old element from the list

Parameters

old_elem

to be erased from the list

                             {
    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;
    }
}

Here is the call graph for this function:

insert()

void 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

                           {
    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";
    }
}

Here is the call graph for this function:

isEmpty() [1/2]

bool list::isEmpty

(

)

function checks if list is empty

Returns

true if list is empty

false if list is not empty

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

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

{ return head == nullptr; }

operator=()

list & list::operator=

(

const list &

other

)

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

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

Here is the call graph for this function:

push_back()

void 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

                                 {
    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();
    }
}

Here is the call graph for this function:

push_front()

void 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

                                  {
    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;
    }
}

Here is the call graph for this function:

reverseList()

void list::reverseList

(

)

Utility function for reversing a list.

Using the current, previous, and next pointer.

Returns

void

                       {
    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 > list::search

(

int

find_elem

)

function searchs for

Parameters

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

                                              {
    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();
}

Here is the call graph for this function:

top()

int32_t list::top

(

)

const

Utility function to find the top element of the list.

Returns

the top element of the list

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

Here is the call graph for this function:

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

                                          {
    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

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

---

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

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