#Adding new item to list time complexity

3 messages · Page 1 of 1 (latest)

night stream
#

template<typename T>
void List<T>::push_back(T data)
{
if (m_Head == nullptr)
m_Head = new Node<T>(data);
else
{
Node<T>* current = m_Head;

    while (current->pNext)
        current = current->pNext;

    current->pNext = new Node<T>(data);
}

}

Why people say that time complexity for adding new element to list is O(1) when here we have to iterate through the list to add new element, so shouldn`t it be O(n)?

final apexBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

heady coral
#

Lists store the length of the list as a field. So assuming the appended item will fit the current allocated memory for the list no iteration is needed.