Hardware: Using Timer Interrupts
Software: Dynamic Data Structures
Anything that stores data can be called as a data strucutre.
"Dynamic data structures are data structures that can grow and shrink during the execution of a program."
Linked Lists
Linear data structure which consists of a group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain.
Advantages
- Dynamic, allocates memory when required
- insertion and deletion easily implemented
- Stacks and queues easily executed
- Reduces access time
Disadvantages
- Memory wasted by pointers (require extra memory)
- No element can be accessed randomly
- reverse traversing difficult
Applications
- Used to implement stacks, queues, graphs, etc.
- Allows you to insert elements at beginning and end of list
- Don't need to know size in advance
Head is pointer that points to the first node in linked list.
To access, use pointer head to reference info in first node, then, since first node contains pointer to next node, we can move to second node. Last node in list will contain pointer value of null to indicate end.
Example 1.1
This example shows show each node in a linked list is represented
struct node
{
int data;
struct node *link;
};
To insert value into linked list, location for insertion must be found. Use pointer to first node to access first data value in the list, and if data value is less than value to be inserted, move to next data value using pointer in current node.
Can be inserted in one of four places:
- Before first node
- Between two nodes
- After last node
- Into empty list
Similar process for deleting value from linked list.
Comments
Post a Comment