Note 05: Structs, Abstraction, and Linked Lists - [Homepage](http://gddh.github.io/)
===================
```
typedef struct s_list
{
struct s_list next;
void *data;
} t_list;
```
## Struct
A data type declaration that defines a list of variables to one pointer. The variables are stored in a continguous block of physical memory pointed to by the pointer. This allows access to each of the variables.
### Syntax
The syntax for declaring a struct:
```
struct tag
{
type member1;
type member2;
/* declare as many members as desired, but the entire structure size must be known to the compiler. */
};
```
To create a single structure. Note that this is exactly like creating an integer.
Note the tag is optional.
```
struct tag name_of_single_structure;
int name_of_integer;
```
Let's consider a dummy example:
```
struct student
{
int age;
char gender;
char *name;
};
```
We've declared a struct called student, which includes three variables, an integer, a character, and a character pointer (a string).
### Struct Pointers and Accessing Struct Variables
We can then access each of the variables. Let's expand on our dummy example.
```
#include <stdio.h>
struct student {
int age;
char gender;
char *name;
};
int main()
{
struct student cur_stud; /* actual student, called cur_stud */
struct student *p; /* A pointer, p, to student type */
p = &cur_stud; /* Because p is a pointer, we must assign an address to it.
/* We refer to the variables directly with the object */
cur_stud.age = 35;
cur_stud.gender = 'f';
cur_stud.name = "annie";
printf("%s is %c and %d\n", cur_stud.name, cur_stud.gender, cur_stud.age);
/* We refer to the variables using a pointer to the object */
p->age = 25;
p->gender = 'm';
p->name = "andy";
printf("%s is %c and %d\n", p->name, p->gender, p->age);
/* We refer to the variables using a pointer to the object. Equivalent to second example */
(*p).age = 30;
(*p).gender = 'f';
(*p).name = "anna";
printf("%s is %c and %d\n", (*p).name, (*p).gender, (*p).age);
}
Output:
$> ./a.out | cat -e
annie is f and 35$
andy is m and 25$
anna is f and 30$
```
## Typedef - Type Definitions
A reserved keyword used to create an alias name for another data type.
### Why Typedef?
Alex Allain makes a very good case in his [explanation](https://www.cprogramming.com/tutorial/typedef.html) of typedef. I've copied what I believe is relevant below.
> For instance, you might have some variables that always store information about the user's current score in a game or how many points the player can get from performing an action like killing an enemy. You might also have some variables that are intended to keep track of the amount of life left for the player and how many life points he can receive for picking up life-enhancers. These two concepts are totally different, and there's no time when you'd ever want to store one type of data--for instance, the number of points--in a variable that is intended for the other type--the amount of life points a player has or can gain.
>
> You know from the start that these two concepts are totally different, even if you store both of them as integers. By thinking of the two types of data as different "data types", you give yourself a useful way to add an element of defensive programming to your code by making it clear what type each variable is associated with--for example, you might prefix all variables storing information about life with an l, and about scores with an s. You'd never expect an assignment from lhigh to shigh--the two concepts are fundamentally incompatible.
As Alex points out, the solution is to use wrapper class, but another partial solution is typedef.
As we will see, it also simplifies usage of structs.
**Takeaway**:```typdef``` provides greater clarity and readability.
### Syntax
Here are some examples
```
/* Giving an alias name, assignment_score, to type int */
typedef int assignment_score;
/* Giving an alias name, age, to type unsigned int */
typedef unsigned int age;
/* Giving an alias name, t_student, to type struct s_student */
typedef struct s_student t_student;
```
## Putting it Together
We can use ```typdef``` directly with struct declaration.
```
typedef struct s_student
{
int age;
char gender;
char *name;
} t_student;
```
What we are doing here is we are declaring a struct, ```s_student``` with the variables ```age```, ```gender```, and ```*name```. We then given the alias name ```t_student``` to```struct s_student```.
By doing so, we don't need to use ```struct``` everytime we use ```s_student```.
We prefix student with t and s because Norm says we should prefix types with ```t``` and structs with ```s```.
Now that we've defined what a student is, we can start storing actual student profiles into ```t_student```.
```
t_student *create_profile(int cur_age, char *cur_name, char cur_gender)
{
t_student *tmp;
tmp = (t_student *)malloc(sizeof(t_student));
if (tmp)
{
tmp->age = cur_age;
tmp->name = cur_name;
tmp->gender = cur_gender;
}
return (tmp);
}
```
Just as we would malloc a new array, we would also malloc a new ```t_student``` to store our information. This also means we must ```free``` it after we are done using that instance of ```t_student```.
## A New Level of Abstraction
Let's say that a student has a birthday. This means that we will need to update the student's profile.
```
void increase_age(t_student *student)
{
student->age = student->age + 1;
}
```
Notice at this point we can and are working on a more abstract level, where we have "objects", ```t_student```, that on an abstract level represent student profiles. In code, we understand them as ```struct``` with three variables, but let's say we created functions such as ```increase_age```, ```compare_name```, ```change_name```, ```compare_age```, ....
With a set of functions that will allow us to operate on ```t_student```, and we can think about ```t_student``` as a student profile rather than a ```struct``` with three variables.
We should abstract away the actual variables and how they are stored. When working at a higher level of abstraction, we want to treat the lower level as a "black box." For example, let's say we are building a program on the level of abstraction where we are thinking about student profiles. If we need the student's age, we shouldn't access it directly with ```student_pointer->age```, we would use a function such as ```get_student_age```. The reason we want to do this will be illustrated by the following example.
### Why Abstraction
Let's say you and a team of coders are writing a program that does analysis on all students and their performance based on age. At this point, you might want to add another another variable in the struct ```t_student```. Thanks to a level of abstraction, you can simply make the change to ```t_student```, make necessary changes to functions on a lower level of abstraction, and add functions such as ```get_level``` without breaking any of the code that you or your team has written. To be clear, the lower level of abstraction are the functions that treat the ```t_student``` as a structure and variables.
Somewhere down the line you realize that the students' age are given to your team as strings, but you and your team have already written all your programs treating the age as an unsigned int. This is fine because all the programs should be using ```t_student``` on a higher level of abstraction, which means the program should not have directly "interacted" with ```t_student```'s structure. Any interaction would have been done using the functions that work on the lower level of abstraction. This means we simply need to modify the functions dealing with age such that they properly process the data (atoi) such that it will return an int. All the programs will still work!
We traded a couple of more functions (and lines of code) for modularity, versatility, and in many cases greater readability.
Never cross these levels of abstraction, no matter how sure you are things won't change. You don't know if somewhere down the line some poor programmer will need to update the code or use the code without knowing you've broken the abstraction barrier.
**Never break abstraction barriers**
## Linked Lists
A good way to understand linked list is to visualize them:
The linked list is composed of nodes, each holding some sort of data and a pointer to the next node, with the exception of the last node, which points to NULL. The linked list in the illustration above holds integers as data.
```
typedef struct s_list
{
struct s_list next;
void *data;
} t_list;
```
Conceptually linked lists are very simple, but they are actually very powerful tools. Linked lists can be used to build stacks, queues, hash tables, and other data structures. We can replace the use of arrays as storage devices with linked lists. This is because arrays are limited by their fixed size, while linked lists memory limit is the amount of free space in memory
Linked List add ons:
- doubly linked lists, where there are pointers pointing to the node in front of it in addition to the node behind it.
- In doing so, we can remove from the beginning or the end
- count
- We can keep track of our size
- sentinel node
- prevent null cases
# Problem Set
For the following exercises, you have to use the following structure :
```
typedef struct s_list
{
struct s_list next;
void *data;
} t_list;
```
I recommend using the following ```.h``` file. Simply ```#include``` it in your ```.c``` file. This way you can test your functions.
```
#ifndef FT_LIST_H
# define FT_LIST_H
#include <stdlib.h>
#include <stdio.h>
typedef struct s_list
{
struct s_list *next;
void *data;
} t_list;
#endif
```
1. Create the function ```ft_create_elem``` which creates a new element of t_list type. It should assign data to the given argument and next to NULL. You can use ```malloc```. Here’s how it should be prototyped:
```t_list *ft_create_elem(void *data);```
2. Create the function ```print_list``` which prints the linked list followed by a new line. If the list is empty, then it should print a new line. You can use ```printf```. This is really a function for you to visualize whether the following functions work, so feel free to make the visualization as nice as you'd like. Assume that the data is strings. Here's how it should be prototyped: ```void print_list(t_list *begin_list);```
3. Create the function ft_list_push_back which adds a new element of t_list type at the end of the list. It should assign data to the given argument. You can only use ```ft_create_elem```. If necessary, it’ll update the pointer at the beginning of the list. Here’s how it should be prototyped : ```void ft_list_push_back(t_list **begin_list, void *data);```
4. Create the function ft_list_push_front which adds a new element of type t_list to the beginning of the list. It should assign data to the given argument. You can only use ```ft_create_elem```. If necessary, it’ll update the pointer at the beginning of the list. Here’s how it should be prototyped : ```void ft_list_push_front(t_list **begin_list, void *data);```
5. Create the function ft_list_size which returns the number of elements in the list. Here’s how it should be prototyped : ```int ft_list_size(t_list *begin_list);```
6. Create the function ft_list_last which returns the last element of the list. Here’s how it should be prototyped : ```t_list *ft_list_last(t_list *begin_list);```
7. Create the function ft_list_clear which clears all links from the list. It’ll then assign the list’s pointer to null. You are allowed to use ```free```. Here’s how it should be prototyped : ```void ft_list_clear(t_list **begin_list);```
8. Create the function ft_pop which "pops" off the first node from the list. The function will free the first node and return the data in first node. The beginning of the list should be the next node or null if there is no next node. Here's how it should be prototyped : ```void *ft_pop(t_list **begin_list);```
9. Create the function ft_list_at which returns the Nth element of the list. In case of error, it should return a null pointer. 0 is the first element. Here’s how it should be prototyped : ```t_list *ft_list_at(t_list *begin_list, unsigned int nbr);```
10. Create the function ft_list_reverse which reverses the order of a list’s elements. You may only use pointers related stuff. ```void ft_list_reverse(t_list **begin_list);```
11. Create the function ft_list_merge which places elements of a list begin2 at the end of an other list begin1. Element creation is not authorised.
If ```begin_list1``` is empty and ```begin_list2``` is not, ```begin_list1``` should point to ```begin_list2```. If ```begin_list2``` is empty, nothing should happen to ```begin_list1.``` If they are both empty, nothing should happen.
Here’s how it should be prototyped: ```void ft_list_merge(t_list **begin_list1, t_list *begin_list2);```
# Problem Set Sol
1. create_elem
```
t_list *ft_create_elem(void *data)
{
t_list *tmp;
tmp = (t_list *)malloc(sizeof(t_list));
if (tmp)
{
tmp->data = data;
tmp->next = NULL;
}
return (tmp);
}
```
2. print_list
```
void print_list(t_list *begin_list)
{
t_list *list;
list = begin_list;
while (list)
{
printf("%s-->", list->data);
list = list->next;
}
printf("\n");
}
```
3. ft_list_push_back
```
void ft_list_push_back(t_list **begin_list, void *data)
{
t_list *list;
list = *begin_list;
if (list)
{
while (list->next)
list = list->next;
list->next = ft_create_elem(data);
}
else
{
*begin_list = ft_create_elem(data);
}
}
```
4. ft_list_push_front
```
void ft_list_push_front(t_list **begin_list, void *data)
{
t_list *list;
if (*begin_list)
{
list = ft_create_elem(data);
list->next = *begin_list;
*begin_list = list;
}
else
*begin_list = ft_create_elem(data);
}
```
5. ft_list_size
```
int ft_list_size(t_list *begin_list)
{
int count;
t_list *list;
count = 0;
list = begin_list;
while (list)
{
count = count + 1;
list = list->next;
}
return (count);
}
```
6. ft_list_last
```
t_list *ft_list_last(t_list *begin_list)
{
t_list *list;
if (begin_list)
{
list = begin_list;
while (list->next)
list = list->next;
return list;
}
return begin_list;
}
```
7. ft_list_clear
```
void ft_list_clear(t_list **begin)
{
t_list *prev;
while (*begin)
{
prev = *begin;
*begin = (*begin)->next;
free(prev);
}
}
```
8. ft_pop
```
void *pop(t_list **begin_list)
{
t_list *tmp;
void *data;
if (*begin_list)
{
tmp = *begin_list;
*begin_list = (*begin_list)->next;
data = tmp->data;
free(tmp);
return data;
}
return (NULL);
}
```
9. ft_list_at
```
t_list *ft_list_at(t_list *begin_list, unsigned int nbr)
{
t_list *list;
list = begin_list;
while (list && nbr > 0)
{
list = list->next;
nbr = nbr - 1;
}
return list;
}
```
10. ft_list_reverse
```
void ft_list_reverse(t_list **begin_list)
{
t_list *prev;
t_list *cur;
t_list *next;
if (*begin_list)
{
prev = *begin_list;
cur = (*begin_list)->next;
while(cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
(*begin_list)->next = NULL;
*begin_list = prev;
}
}
```
11. ft_list_merge
```
void ft_list_merge(t_list **begin_list1, t_list **begin_list2)
{
t_list *list;
list = *begin_list1;
if (list)
{
while (list->next)
list = list->next;
list->next = *begin_list2;
}
else
{
*begin_list1 = *begin_list2;
}
}
```
------------------------------
Sources: Wikipedia, GeeksForGeeks, Cprogramming.com, StackOverflow, Berkeley CS, School 42
Sign in with Wallet
Connect another wallet