Skip to main content

Day 22: More with Timers | Dynamic Data Structures

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

Popular posts from this blog

Day 20: Structures, Programming with Pointers

Lecture Structures Structure defines set of data, but individual parts do not have to be the same type. Example 1.1 struct hurricane {  char name[10];  int year,category; }; Within a structure, variables and even arrays can be defined. Structures are also known as aggregate data types since multiple data values can be collected into a single data type. Individual values within a structure are called data members, and each member is given a name. In Example 1.1, the names of the data members are name, year, and category. To refer to a data member, the structure variable name followed by a period and a data member name is used.  Definition and Initialization Define structure. Keyword struct used to define name of structure (aka structure tag) and data members that are included in structure After structure defined, structure variables can be defined using declaration statements. Semicolon required after structure definition. Statements can appear before m...
Post a Comment
Read more

Day 6: Analog Sensors | Functions and Modularity

Functions Functions are sets of statements that typically perform operation or compute value. They can help to make programs more accessible and usable for non-programmers e.g. create function that allows user to type "go forward" and move a robot forward. Modules -Functions can be split up into modules, "divide and conquer" -Each module has specific purpose, can be written and tested separately -Smaller than complete solution, therefore testing is easier -Can be used in new problem solutions without being retested -Reduces overall length of program -Allows for increased collaboration; modules can be worked on in parallel Debugging Longer Programs Use a compiler that gives meaningful information about errors. Adding comments around some sections of code can allow for better focus on other parts of the program. Test complicated functions by themselves. Programmer Defined Functions Execution of program always begins with main function. Additional ...
Post a Comment
Read more

Day 7: Random Numbers and Recursion | Sound

Lecture Random Numbers Random numbers can be generated using the rand function, however, the same value would be printed since it generates integers in a specified sequence. To generate a new sequence of random numbers each time, a new random-number seed is needed. First, I need to use srand to generate a seed in order for the rand function to generate new random numbers every time. We can also generate random integers between specified limits.  #include <stdio.h> #include <stdlib.h> int main(void) {   /* Declare variables and function prototype. */   unsigned int seed;   int a, b, k;   int rand_int(int a,int b);   /* Get seed value and interval limits. */   printf("Enter a positive integer seed value: \n");   scanf("%u",&seed);   srand(seed);   printf("Enter integer limits a and b (a<b): \n");   scanf("%i %i",&a,&b);   /* Generate and print ten random numbe...
Post a Comment
Read more