Linked List Past Paper PDF

# علوم الحاسب ## الفرقة الثانية ### Session 6 ### هياكل البيانات ### Data Structures ## Q.1. Define linked list, state types, characteristics, and operations. Linked list chain of nodes, where every node points to the next node. - First pointer called **first/head**. - Each link is linked with i...

# علوم الحاسب ## الفرقة الثانية ### Session 6 ### هياكل البيانات ### Data Structures ## Q.1. Define linked list, state types, characteristics, and operations. Linked list chain of nodes, where every node points to the next node. - First pointer called **first/head**. - Each link is linked with its next link using its **next** link. - The last link carries a link as **null** to mark the end of the list. - Because each node of a linked list has two components, we need to declare each node as a **class** or **struct**. ``` struct nodeType { int info; node Type *link; }; ``` ### Types of Linked List - **Simple Linked List**: Item navigation is forward only. - **Doubly Linked List**: Items can be navigated forward and backward. - **Circular Linked List**: Last item contains link of the first element as next and the first element has a link to the last element as previous. ### Basic Operations: - **Insertion**: Adds an element at the beginning of the list. - **Deletion**: Deletes an element at the beginning of the list. - **Display**: Displays the complete list. - **Search**: Searches for an element using the given key. - **Delete**: Deletes an element using the given key. ## Q.2. Answer the following question using the next linked list. ``` head 2000 2000 2800 1500 3600 17 2800 92 1500- 63 3600 45 0 info link info link info link info link ``` 1. head 2000 2. head->info 17 3. head->link 2800 4. head->link->info 92 ### Linked list operations 1. **Insertion Operation** - Inserting (NewNode), between (LeftNode) and (RightNode). - NewNode.next -> RightNode; - Now, the next node at the left should point to the new node. 2. **Deleting Operation** - First, locate the target node to be removed, by using searching algorithm. - The left node of the target node point to the next node of the target node. - LeftNode.next -> TargetNode.next; - TargetNode.next -> NULL; - We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory. 3. **Reverse Operation** - We need to make the last node to be pointed by the head node and reverse the whole linked list. - First, we traverse to the end of the list, (pointing to NULL). - Now, we shall make it point to its previous node. ## Q.3. Create linked list for storing three integers n1, n2, n3. ``` struct node { int data; struct node *next; }; struct node *head = NULL; struct node *n1, n2, *n3; n1 = (struct node *) malloc(sizeof(struct node)); n2 = (struct node *) malloc(sizeof(struct node)); n3 = (struct node *) malloc(sizeof(struct node)); head = n1; n1->data = 1; n1->next = n2; n2->data = 2; n2->next = n3; n3->data = 3; n3->next = NULL; /* <-- indicates end of list */ ``` ### Linked-list implementation ``` #include <iostream> using namespace std; struct node { int data; int key; struct node *next; }; struct node *head = NULL; struct node *current = NULL; void insertFirst(int key, int data) { struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key: link->data = data; link->next = head; head = link; } ``` ``` void printList() { struct node *ptr = head; cout << "\n[ "; while (ptr != NULL) { cout << ptr->key << "," << ptr->data << "\t"; ptr = ptr->next; } cout << "]"; } struct node* deleteFirst() { struct node *tempLink = head; head = head->next; return tempLink; } bool isEmpty() { return head == NULL; } int length() { int length = 0; struct node *current; for (current = head; current != NULL; current = current->next) { length++; } return length; } ``` ``` struct node* find(int key) { struct node* current = head; if (head == NULL) { return NULL; } while (current->key != key) { if (current->next == NULL) { return NULL; } else { current = current->next; } } return current; } ``` ``` struct node* delet(int key) { struct node* current = head; struct node* previous = NULL; if (head == NULL) { return NULL; } while (current->key != key) { if (current->next == NULL) { return NULL; } else { previous = current; current = current->next; } } // Delete if (current == head) { head = head->next; } else { previous->next = current->next; } return current; } ``` ``` void sort() { int i, j, k, tempKey, tempData; struct node *current; struct node *next; int size = length(); k = size; for (i = 0; i < size - 1; i++, k--) { current = head; next = head->next; { for (j = 1; j < k; j++) if (current->data > next->data) { tempData = current->data; current->data = next->data; next->data = tempData; tempkey = current->key; current->key = next->key; next->key = tempkey; } current = current->next; next = next->next; } } } ``` ## Polynomial List - Expression consists of two parts: - One is the coefficient. - Other is the exponent. - 10x² + 26x - 10 and 26 are coefficients. - 2, 1 are its exponential value. - The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent. [True] - Polynomial can be represented in the various ways: - Using arrays. - Using Linked List. ### Representation of Polynomial Using Linked Lists: - Coefficient: 4x³ + 6x² + 10x + 6 - Power: 4 3 6 2 10 1 6 0 ## Q.4. Given two polynomial numbers represented by a linked list. Write a function that add these lists means add the coefficients who have same variable powers. ### Input: - 1st number = 5x^2 + 4x^1 + 2x^0 - 2nd number = 5x^1 + 5x^0 ### Output: - 5x^2 + 9x^1 + 7x^0 ### Input: - 1st number = 5x^3 + 4x^2 + 2x^0 - 2nd number = 5x^1 + 5x^0 ### Output: - 5x^3 + 4x^2 + 5x^1 + 7x^0 ### Input: - 1st number = 5x^2 + 4x^1 + 2x^0 - 2nd number = 5x^1 + 5x^0 ### Output: - 5x^2 + 9x^1 + 7x^0 ``` List1 524120 NULL List 2 + 5150 NULL 1 Resultant List 529370 NULL NODE Coefficient STRUCTURE Power Address of next node ``` ``` #include <iostream> using namespace std; struct Node { int coeff; int pow; struct Node* next; }; void create_node(int x, int y, struct Node** temp) { struct Node *r, *z; z = *temp; if (z == NULL) { r = (struct Node*)malloc(sizeof(struct Node)); r->coeff = x; r->pow = y; *temp = r; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } else { r->coeff = x; r->pow = y; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } } ``` ``` void polyadd(struct Node* poly1, struct Node* poly2, struct Node* poly) { while (poly1->next && poly2->next) { if (poly1->pow > poly2->pow) { poly->pow = poly1->pow; poly->coeff = poly1->coeff; poly1 = poly1->next; } else if (poly1->pow < poly2->pow) { poly->pow = poly2->pow; poly->coeff = poly2->coeff; poly2 = poly2->next; } else { poly->pow = poly1->pow; poly->coeff = poly1->coeff + poly2->coeff; poly1 = poly1->next; poly2 = poly2->next; } } poly->next= (struct Node*)malloc(sizeof(struct Node)); poly = poly->next; poly->next = NULL; while (poly1->next || poly2->next) { if (poly1->next) { poly->pow = poly1->pow; poly->coeff = poly1->coeff; poly1 = poly1->next; } if (poly2->next) { poly->pow = poly2->pow; poly->coeff = poly2->coeff; poly2 = poly2->next; } poly->next = (struct Node*)malloc(sizeof(struct Node)); poly = poly->next; poly->next = NULL; } } ``` ``` void show(struct Node* node) { while (node->next != NULL) { cout<< node->coeff, node->pow; node = node->next; if (node->coeff >= 0) { if (node->next != NULL) cout<<"+"; } } } int main() { struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; create_node(5, 2, &poly1); create_node(4, 1, &poly1); create_node(2, 0, &poly1); create_node(-5, 1, &poly2); create_node(-5, 0, &poly2); cout<<"1st Number: "; show(poly1); cout<<"\n2nd Number: "; show(poly2); poly = (struct Node*)malloc(sizeof(struct Node)); polyadd(poly1, poly2, poly); cout<<"\nAdded polynomial: "; show(poly); return 0; } ```