#Reading linked list stack backwards download
#Reading linked list stack backwards free

This ensure that no traversal is needed for both operation. When implementing with linked list, enqueue (adding data) happens at tail and dequeue (removing data) happens at head.

A person getting into line is “enqueued”, and a person getting out of line is “dequeued”.Įnqueue O(1), Dequeue O(1). The first person in line is the first person to get out of line. Adding a piece of paper is called “pushing”, and removing a piece of paper is called “popping”. The last piece put into the stack is on the top, so it is the first one to come out. Stack and Queue are abstract data type that has different accesing protocols. search() - search list and return the array that containt the position of the value that matched, index start at 0 O(n).reverse() - reverses the list, reverse_recursion() - reverse the list using recursion O(n).search(value) - return an a list containing the indexes of every items that match the value O(n).erase(index) - removes node at given index O(n).insert(index, value) - insert value at index, so current item at that index is pointed to by new item at index O(n).pop_back() - removes end item and returns its value O(n).push_back(value) - adds an item at the end O(1).pop_front() - remove front item and return its value O(1).push_front(value) - adds an item to the front of the list O(1).value_at(index) - returns the value of the nth item (starting at 0 for first) O(n).

is_empty() - bool returns true if empty - O(1).

size() - returns number of data elements in list - O(n).

These implementations are done individually and independent to each other

Insert O(1), indexing (finding the node) is O(n).

So if we want to access an element in between, we need to start to ask the first node. Good thing is that each node cost small memory and all nodes doesnt take a long chunk in memory.Īlthought the total memory is a bit larger (carry a pointer every element), if data is big, carrying a pointer is not a big dealįirst node: Head node, this gives access of completed list Linked list is non-consecutive nodes in memory, each node stores the actual data and the link to the next node (the address of the next node).

Add, when array reaches max size, we need to copy all elements into new array: O(n), when not max size, it costs O(1).

Remove, remove first element cost O(n) and remove last element costs O(1).

Insert, worst case is insert at the first position so all elements are shifted: O(n), insert at last position costs O(1).

Access: read/write element at any position: O(1) - best thing about array.

Insertion and deletion make almost all element moved/shifted

#Reading linked list stack backwards free

When array is full, we need to create a new array with double the size and free the memory for former array. Arrayįixed size, contain elements of same data type.

#Reading linked list stack backwards download

Download Jupyter/IPython Notebook here Comparing Array and Linked List 1.