Algorithm and Data structure:Linear Lists

Goals of studying Data Structures:
–To identify and develop useful mathematical entities and
operations and to determine what classes of problems can be
solve by using these entities and operations
•This goals views a high-level data type as a tool that can be used to solve other problems
–To determine representations of those abstract entities and to
implement the abstract operations on these concrete
representations
•This goals views the implementation of such a data type as a problem to be solve using already existing data types


Abstract Data Type
•Data type = a collection of values and a set of operations on those values.
•Some instance of data types are integer, character, string, float and double.
•Abstract = conceptual solution to a specific problem. The conceptual solutions must be independent from the implementation.
•Abstract Data Type (ADT) = the basic mathematical concept that define the data type.
•ADT is not concern with implementation at all, not even the type of programming languages used.
•ADT is a useful guideline to implementers and a useful tool to programmers who wish to use the data type correctly
•Two parts of ADT:
–Value definition: define the collection of values of the ADT
–Operator definition: define the operations, which can be performed on the data type
•The reason for creating ADT is to aid programmers to solve problem


Arrays
•Array is called composite or structured data type.
•It is a collection of similar data type arranged in order.
•Two basic operations for array:
–Extraction: is a function that accepts an array, a, and an index, i, and returns an elements of the array
–Storing: accepts an array,a , an index, i, and an element, x.
•Elements of an array’s index:
–Lower bound: the smallest element of an array’s index.
–upper bound: the highest element.
–Range: the number of elements in an array
•Formula: range = upper bound – lower bound + 1


Linked Lists
•A list is a collection of values arranged in sequence
•Array is a data type suitable of representing a list, however, using arrays, we are implementing the list using static data structure
•Link list is use to represent list in dynamic data structure
•Linked list is a linear collection of self-referential structures, called nodes, connected by pointer links
•Advantages of linked list:
–A linked list is appropriate when the number of data elements to be represents in the data structure at once is unpredictable.
–Linked list are dynamic, so the length of a list can increase or decrease as necessary
–Linked list become full when the system has insufficient memory to satisfy dynamic storage allocation requests

•Pointers
•Self-Referential Structures
•Dynamic Memory Allocation
•Linked List
•Implementation of Linked List
•Traverse a Linked List
•Advanced Link List
•Linked List in Applications
•Weakness of Link List

•List is usually refers as a sequence of similar elements, for example a list of student names, a list of books
•In computer, list can be easily represented using array. For example, a list of integer can be represented in an array of integer
•Linked list consists of a series of structures, which are not necessarily adjacent in memory.
•Each structure is link to its adjacent structure (predecessor) through a self-referential pointer.
•Linked list as a linear collection of self-referential structures, called nodes.
•Subsequent nodes are accessed via the link pointer member stored in each node. By convention, the link pointer in the last node of a list is set to NULL to mark the end of the list.


Implementation of Linked List
•Deleting A Node
–Delete a node requires 3 pointers.
–currentPtr and previousPtr for transversal, and a temporary pointer to store the node temporary, before we delete it from the list.
–Deleting requires a temporary hold the node, which we need to delete.
–Deleting a node does not remove it from the memory until we free it from the memory using free(tempPtr) command

Traverse A Linked List
•Traverse means moving from one node to another continuously.
•To traverse a linked list, we need to use a pointer to move from one node to another.
•The algorithm to traverse linked list and search for matching elements .


Advance Linked List
•Expansion of linked list:
–Circular Linked List
–Double Linked List
–Skip List

Linked List In Applications
•Linked list can be view as dynamic and non-contiguous array
•Linked list adds the capability of dynamic space allocation and efficient insertion and deletion process
•Typically linked list is important for databases, moreover, it usually use as supporting ADT to become the enabler for other ADT
•Some of the ADT that use list are Stack, Queue, Tree and Graph


Weakness of Linked List
•Weaknesses of linked list compare to array is in searching and data retrieval
•Because linked list is not indexed, there is no way to retrieve a data unless to transverse the whole list
•If the data located in the beginning of the list, the problem is not significant
•However, if the data is located at the end of the list, it may seriously affect the program performance
•Array on the other hand is indexed. Program can be easily access to an array element if it knows the index of the elements