Algorithms and Data Structures on Python - Notes 2

 Linked list

It needs a node class

It should have 2 basic characteristic

* Data

* Reference to the next node

It can be used to implement stack or queues. It does not allow random access as like in Array.

Obtaining a last node, locating a particular node requires an iteration over all or most of the items in the linked list. 

Advantage

* It is dynamic data structures(No need to specify size)

* It can allocate memory on run time

* It take O(1) constant time complexity to insert an item at the beggining or removing at the beggining, unlike array where as its O(n)

* Linked list can grow organically, unlike in array where we need o(n) for re-sizing here its just about updating the reference 

Disadvantages.

* Waste of memory due to references

* Nodes in the linked list must be read in order from the beginning as linked list have sequential access

* Difficult to do reverse travel , but we can enable this with back pointer. But this takes a memory

 

Inserting a references

* Inserting to the beginning takes O(1) constant time complexity. Because its just about adding a node

updating its next reference to the start of the linked list

* Inserting to the last node O(n) time complexity because we need to traverse throughout the linked list

to get to the last node, where last node will be pointing to a NULL reference. NULL reference is very much 

important in terms of linked list because that will be the last node of the linked list

Remove

Removing at the beginning is always fast because we don't need to search for item. Its 

only about removing, eg. In java assign to null.

Removing at a given point is O(n) linear time complexity.   

Algorithms and Data Structures on Python - Notes 1

 

         Data Structures Overview  

          Bad programmers worry about code , good programmers worry about data structures and their relationships! 

       Data structures provide efficient ways to store data. A proper data structure can boost an Algorithm. If we need to make a app performs good then we must care about selecting proper data structure.

     There is a tradeoff between running time complexity and memory time complexity. Eg. Dijktras algorithm with priority queue performs better but it will take more memory. If we need to minimize the memory then the application will be slow.

          Abstract data types  -  Data Structures 

Abstract data type is basically the logical implementation. We can use data structures like array or linked list to implement it. So Abstract data types are logical definition  and data structures are concrete implementations. This is the difference between abstract data types and data structures.

Arrays - Basics

         It can be N dimensional according to the needs. Arrays are good because it has O(1) time complexity to get by index. 

  Disadvantages are 

1. It is compile-time : it is no so dynamic data structures.
2. If it is full we need to create a bigger array to copy the contents. That operation is going to take O(N) time complexity
3. It is not able to store items with different type

Arrays - Operations

       Add : We can do it in O(1) constant time complexity because we are going to insert the element at the end of the array. And we certainly we should know the location where we are inserting.

                 If we insert to middle of  of the array, then we have to shift entire array and we ends up O(N) linear time complexity. 

       Remove : If we remove the last item then we will be able to do it on O(1). But to remove an item with a particular index then shifting is involved so we will end up with O(N). 

      Arrays are good data structures? It depends on the application it uses

Examples : pylearn_personal_git