4 What is the time complexity of inserting into the front of

4. What is the time complexity of inserting into the front of a linked list of size N, given the front of the list and a value to insert?

What is the time complexity of inserting into the back of a linked list of size N, given the front of the list and a value to insert?

5. Complete the definition of the following function:

// doubleArray(array,size)

// doubles the size of the passed dynamic array and copies all old elements into the new array

template <class datatype>

void doubleArray(datatype * &array, unsigned int &size)

{

}

6. Complete the definition for the following function that inserts the passed value onto the top of the passed dynamic array. You may use the doubleArray function from the other question.

// arrayStackInsert( array, size, value) inserts the value on the ‘top’ of the dynamic array

template < class datatype>

void arrayStackInsert( datatype * &array,

                    unsigned int &size,

                     datatype const & value)

}

}

7.

Write the definition to insert the passed value on top of the passed stack in the following function:

// Node<datatype> contains datatype data;

//Node<datatype> * next;

template <class datatype>

void ListStackInsert(Node<datatype> * &stack,

datatype const & value)

{

}

Solution

Complexity of unsorted linked list and sorted linkedlist may vary
depending upon the cost to add or delete an element into a known location in the list
(i.e. if you have an iterator to the location) is O(1).
If you don\'t know the location, then you need to traverse the list to the location
of deletion/insertion, which takes O(n) time.
I guess I will start you off with the time complexity of a linked list:

Indexing---->O(n)
Inserting / Deleting at end---->O(1) or O(n)
Inserting / Deleting in middle--->O(1) with iterator O(n) with out

The time complexity for the Inserting at the end depends if you have the location
of the last node, if you do, it would be O(1) other wise you will have to search
through the linked list and the time complexity would jump to O(n).

The time complexity to insert into a doubly linked list is O(1) if you know the
index you need to insert at. If you do not, you have to iterate over all elements
until you find the one you want. Doubly linked lists have all the benefits of arrays
and lists:
They can be added to in O(1) and removed from in O(1), providing you know
the index. If the index to insert/remove at is unknown, O(n) is required.
Note that finding an element always takes O(n) if your list is unsorted (log(n) otherwise)