data_structures::linked_list::list Class Reference

Collaboration diagram for data_structures::linked_list::list:

Public Member Functions
	list ()
bool	isEmpty ()
	Utility function that checks if the list is empty. More...
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 ()
	list ()
bool	isEmpty ()
void	insert (int32_t new_elem)
	Utility function that adds a new element at the end of the list. More...
void	reverseList ()
	Utility function for reversing a list. More...
void	display ()
int32_t	top ()
	Utility function to find the top element of the list. More...
int32_t	last ()
int32_t	traverse (int32_t index)
	Utility function to find the i th element of the list. More...

Private Attributes
std::shared_ptr< link >	first
	link before the actual first element
std::shared_ptr< link >	last
	last link on the list More...
Node *	head

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() [2/2]

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

inline

List constructor. Initializes the first link.

           {
        head = nullptr;  // Initialize the first link
    }

Member Function Documentation

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

bool list::isEmpty

(

)

Utility function that checks if the list is empty.

function checks if list is empty

Returns

true if list is empty

false if list is not empty

true if the list is empty

false if the list is not empty

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

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, *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

(

)

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

)

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