# Week 3 - Linked Lists
## Team
Team name: Error
Date: 8th March 2022
Members
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. |Minh 511907 |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Hoa 487272 |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Thanh 516467 |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Kaloyan 511216 |
## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.
Set up a project in CLion to write the small programs needed in some of the activities.
### Activity 1: Pointers to pointers
Record your answer here
| Variable | Address | Value |
| ----------- | --------------------- | ----------- |
| value | 0x7ffccb24c954 | 42 |
| ptr | 0x7ffccb24c958 | 42 |
| pptr | 0x7ffccb24c960 | 42 |
| ppptr | 0x7ffccb24c968 | 42 |
Explain: The value of ppptr represent that this pointer pointing to pptr which store the address of ptr and pointing to ptr. Ptr store the address of value and when derefference ptr can retrieve the value of "value" which is 42. Hence
***ppptr -> **pptr -> *ptr -> value
### Activity 2: Chaining pointers
```c
typedef struct node_t {
int value;
struct node_t *next;
} node;
int main(void) {
node fourth = {.value = 42, .next = NULL};
node third = {.value = 7, .next = &fourth};
node second = {.value = 3, .next = &third};
node first = {.value = 2, .next = &second};
struct node_t *ptr;
ptr = &first;
printf("first: %d\n", ptr-> value);
printf("second: %d\n", ptr-> next-> value);
printf("third: %d\n", ptr-> next-> next-> value);
printf("fourth: %d\n", ptr-> next-> next-> next-> value);
return 0;
}
```
### Activity 3: Traversal
```c
int main() {
node fourth = {.value = 42, .next = NULL};
node third = {.value = 7, .next = &fourth};
node second = {.value = 3, .next = &third};
node first = {.value = 2, .next = &second};
struct node_t *ptr;
ptr = malloc(sizeof(struct node_t));
ptr = &first;
struct node_t *temp = NULL;
temp = malloc(sizeof (struct node_t));
temp = ptr;
int count = 0;
while(temp != NULL){
count++;
temp = temp->next;
}
for(int i = 1;i <= count; i++){
printf("%d\n", ptr-> value);
ptr = ptr-> next;
}
free(ptr);
free(temp);
return 0;
}
```
### Activity 4: Linked list deallocation
```c
void list_free(list ** plist) {
free(*plist);
*plist = NULL;
}
```
Although the code still has no-error, it fails to deallocate all the node in the list. The program just deallocates 2 pointers: head and tail pointers which point to node in link list. So other nodes which are between head and tail are still left
So here is the code to delete all the node:
```c
void list_free(list**plist){
while((*plist)->head!=(*plist)->tail){
node*cur=(*plist)->head;
(*plist)->head=(*plist)->head->next;
free(cur);
}
free(*plist);
*plist=NULL;
}
```
The program will create a temporary node which point to the first node and then, the head node will change to next node, the current node will be deleted.
### Activity 5: Prepending
```c
void list_prepend(list*plist,int value){
if(plist->head==NULL){
node_init(&plist->head,value);
plist->tail=plist->head;
}
else{
node*temp=NULL;
node_init(&temp,value);
temp->next=plist->head;
plist->head=temp;
}
}
```
Firstly, it need to check if the plist is NULL or not to decide to create a new node. If there is already a node, then it will create a temporary node to store the new node, and then link the new node to the head node, then change the pointer from head node to new node.
### Activity 6: Time complexity of prepend and append
The time complexity of appending new if we already have pointer to the end of the node is O(1).
However, the time complexity of appending a new node if we would not keep track of the tail is O(n). Because we have to travel until the end of the list so as to insert the node.
### Activity 7: Access by index
Record your answer here
```c
const node*list_at(const list*plist,int index){
node*temp=plist->head;
for(int i=0;i<index;i++){
temp=temp->next;
}
return temp;
}
```
The function will create a temporary node first to point to first node in the linked list. Then it will travel until the index. If the index is out of range, because we let the final node in the link list point to NULL, so the temporary node will also become NULL.
### Activity 8: Time complexity of accessing by index
The time complexity of list_at(const list *plist, int index) function will be between O(1) and O(n) and n is the number of elements in the list. This is because the element we need to find may be at the first index or at the last.
### Activity 9: A bad for-loop
The for-loop n this activity is bad because it is a nested one, which means that it will run while there is another for loop running inside it. This will result in worst-time complexity O(n2) (n to the power of 2).
### Activity 10: Removal in a singly-linked list
Record your answer here
```c
void list_remove_last(list *plist) {
for (int i = 0; i < sizeof(list); i++) {
if ((plist + i)->tail == NULL) {
if (i != 0) {
(plist - 1)->tail->next = plist->tail;
} else {
(plist + i)->tail = plist->tail = plist->head;//one single element
}
}
}
node_free(&plist->tail);
}
```
### Activity 11: Code update - I
```c
typedef struct node_t {
int value;
struct node_t *next;
struct node_t *previous;///////New
} node;
void node_init(node **ptr, int value) {
node *p = (node *) malloc(sizeof(node));
if (p != NULL) {
p->next = NULL;
p->value = value;
p->previous = NULL;//////////New
}
*ptr = p;
}
```
### Activity 12: Code update - II
Record your answer here
```c
void list_prepend(list**plist,int value){
struct node_t*temp=NULL;
node_init(&temp,value);
temp->prev=NULL;
if((*plist)->head==NULL){
(*plist)->head=temp;
(*plist)->tail=temp;
}
else{
(*plist)->head->prev=temp;
temp->next=(*plist)->head;
(*plist)->head=temp;
}
}
```
### Activity 13: Implementation of removal
Record your answer here
```c
// updates the list by removing the node referred to by pnode from the list
void list_remove(list *plist, node * pnode)
{
/* base case */
if (plist == NULL || pnode == NULL)
return;
/* If node to be deleted is head node */
if (plist->head == pnode){
plist->head = pnode->next;
}
/* Change next only if node to be deleted is NOT the last node */
if (pnode->next != NULL) {
pnode->next->prev = pnode->prev;
}
/* Change prev only if node to be deleted is NOT the first node */
if (pnode->prev != NULL) {
pnode->prev->next = pnode->next;
}
/* Finally, free the memory occupied by pnode*/
free(pnode);
}
```
### Activity 14: Implementing insertion
Record your answer here
```c
// updates the list by inserting value before the node referred to by pInsertionPoint
void list_insert(list *plist, node *pbefore, node *pnode) {
pnode->next = pbefore;
pnode->prev = pbefore->prev;
if(pbefore->prev != NULL){
pbefore->prev->next = pnode;
}
else {
plist->head = pnode;
pnode->prev = NULL;
}
pbefore->prev = pnode;
}
```
### Activity 15: Time complexities
Record your answer here
| Operation | Array | Linked List |
| --------------- | -------------------------- | ----------- |
| Access | 0(1) | 0(N) |
| Append | 0(N) | 0(1) |
| Insert | 0(N) | 0(N) |
| Remove | 0(N) | 0(N) |
## Looking back
### What we've learnt
- understand how pointer to pointer work
- be able to retrieve elements from a linked list
- recognize the differences between singly and doubly linked lists
- run a doubly linked list
### What were the surprises
Nothing
### What problems we've encountered
Nothing
### What was or still is unclear
Everything is quite clear
### How did the group perform?
Well group collaboration
> Written with [StackEdit](https://stackedit.io/).
Sign in with Wallet
Connect another wallet