Question

Briefly distinguish between Arrays and Linked List. Write an algorithm for each as well as develop...

Briefly distinguish between Arrays and Linked List. Write an algorithm for each as well as develop computer programs that implement each of them. Show the results of your output including your code.

Homework Answers

Answer #1

Answer : Given data

Let's understand how array is different from Linked list.

ARRAY LINKED LIST
Array is a collection of elements of similar data type. Linked List is an ordered collection of elements of same type, which are connected to each other using pointers.

Array supports Random Access, which means elements can be accessed directly using their index, like arr[0] for 1st element, arr[6] for 7th element etc.

Hence, accessing elements in an array is fast with a constant time complexity of O(1).

Linked List supports Sequential Access, which means to access any element/node in a linked list, we have to sequentially traverse the complete linked list, upto that element.

To access nthelement of a linked list, time complexity is O(n).

In an array, elements are stored in contiguous memory locationor consecutive manner in the memory.

In a linked list, new elements can be stored anywhere in the memory.

Address of the memory location allocated to the new element is stored in the previous node of linked list, hence formaing a link between the two nodes/elements.

In array, Insertion and Deletionoperation takes more time, as the memory locations are consecutive and fixed.

In case of linked list, a new element is stored at the first free and available memory location, with only a single overhead step of storing the address of memory location in the previous node of linked list.

Insertion and Deletion operations are fast in linked list.

Memory is allocated as soon as the array is declared, at compile time. It's also known as Static Memory Allocation. Memory is allocated at runtime, as and when a new node is added. It's also known as Dynamic Memory Allocation.
In array, each element is independent and can be accessed using it's index value. In case of a linked list, each node/element points to the next, previous, or maybe both nodes.
Array can single dimensional, two dimensional or multidimensional Linked list can be Linear(Singly), Doublyor Circular linked list.
Size of the array must be specified at time of array decalaration. Size of a Linked list is variable. It grows at runtime, as more nodes are added to it.
Array gets memory allocated in the Stack section. Whereas, linked list gets memory allocated in Heaps

Implementation of Array in a program

algorithm

START
   Step 1 → Take an array A and define its values
   Step 2 → Loop for each value of A
   Step 3 → Add each element to 'sum' variable
   Step 4 → After the loop finishes, display 'sum'

STOP

IMPLEMENTATION OF ABOVE ALGORITHM IN C PROGRAM


#include <stdio.h>

int main() {
   int array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
   int sum, loop;

   sum = 0;
   
   for(loop = 9; loop >= 0; loop--) {
      sum = sum + array[loop];      
   }

   printf("Sum of array is %d.", sum);   

   return 0;
}

The output should look like this −

Sum of array is 45.

Implementation of linked list in a program

Algorithm:

1.first=new node;{create the 1st node of the list pointed by  first};

                2.Read(Data(first));

                3.NEXT(First)=NULL;

                4.Far a First;   [point Far to the First]

                5. For I=1 to N-1 repeat steps 6 to 10

                6.X=new node;

                7.Read(Data(X))

                8.NEXT(X)=NULL;

                9.NEXT(Far)=X;   {connect the nodes}

                10.Far=X;[shift the pointer to the last node of the list]

                                [end of For Loop]

                11.END


#include <stdio.h>
#include <stdlib.h>

struct node {
   int data;
   struct node *next;
};

struct node *head = NULL;
struct node *current = NULL;

//display the list
void printList() {

   struct node *ptr = head;

   printf("\n[head] =>");
   //start from the beginning
   while(ptr != NULL) {        
      printf(" %d =>",ptr->data);
      ptr = ptr->next;
   }

   printf(" [null]\n");
}

//insert link at the first location
void insert(int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));

   //link->key = key;
   link->data = data;

   //point it to old first node
   link->next = head;

   //point first to new first node
   head = link;
}

int main() {
   insert(10);
   insert(20);
   insert(30);
   insert(1);
   insert(40);
   insert(56); 

   printList();
   return 0;
}

Output

Output of the program should be −

[head] => 56 => 40 => 1 => 30 => 20 => 10 => [null]

_______________THE END________________

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Briefly distinguish between Stack and Queues and write an algorithm for insertion and deletion in stack...
Briefly distinguish between Stack and Queues and write an algorithm for insertion and deletion in stack and queue (PUSH Operation/POP Operation).
Please show the java code and pseudocode as well Describe and implement a recursive algorithm for...
Please show the java code and pseudocode as well Describe and implement a recursive algorithm for reversing a singly linked list L, so that the ordering of the nodes becomes opposite of what it was before. What is the running time of your algorithm on a list of n values? Provide both the growth function and BigOh complexity. Create a driver class to test your implementation.
Write an iterative algorithm in Java-like pseudocode for printing a singly linked list in reverse in...
Write an iterative algorithm in Java-like pseudocode for printing a singly linked list in reverse in O(N) time. You can use as much extra space as you need. The original list pointers CAN NOT BE MODIFIED. State in big-O notation how much extra space is used by this algorithm. Write another iterative algorithm in Java-like pseudocode for printing a singly linked list in reverse using O(1) extra space. The original list pointers CAN NOT BE MODIFIED. This algorithm can have...
Write a C++ recursive function that counts the number of nodes in a singly linked list....
Write a C++ recursive function that counts the number of nodes in a singly linked list. (a) Test your function using different singly linked lists. Include your code. (b) Write a recurrence relation that represents your algorithm. (c) Solve the recurrence relation using the iterating or recursive tree method to obtain the running time of the algorithm in Big-O notation.
C PROGRAMMING Doubly Linked List For this program you’ll implement a doubly linked list of strings....
C PROGRAMMING Doubly Linked List For this program you’ll implement a doubly linked list of strings. You must base your code on the doubly linked list implementation given in my Week 8 slides. Change the code so that instead of an ‘int’ each node stores a string (choose a suitable size). Each node should also have a next node pointer, and previous node pointer. Then write functions to implement the following linked list operations: • A printList function that prints...
Create another list to store your Song objects using a linked list. Show that you understand...
Create another list to store your Song objects using a linked list. Show that you understand how to use pointers and linked list by demonstrating the use of them with the Song objects. 8) Additional criteria for your code - Usability – your code provides users with meaningful messages/prompts for inputs and display of outputs. [3 points] - Accuracy - your code must run and terminate normally. [3 points] - Readability – your code should be well structured and easy...
Please answer in C A doubly linked list is a list in which each entry contains...
Please answer in C A doubly linked list is a list in which each entry contains a pointer to the preceding entry in the list as well as a pointer to the next entry in the list. Define the appropriate structure for the doubly linked list. Write a user space program that implements a doubly linked list and prints out the elements of the list. Develop insert_entry() and remove_entry() functions for this list. The link list should store information on...
C++ please Write code to implement the Karatsuba multiplication algorithm in the file linked in Assignment...
C++ please Write code to implement the Karatsuba multiplication algorithm in the file linked in Assignment 2 (karatsuba.cpp) in Canvas (please do not rename file or use cout/cin statements in your solution). As a reminder, the algorithm uses recursion to produce the results, so make sure you implement it as a recursive function. Please develop your code in small The test program (karatsuba_test.cpp) is also given. PLEASE DO NOT MODIFY THE TEST FILE. KARATSUBA.CPP /* Karatsuba multiplication */ #include <iostream>...
A single linked list is a way to store a collection of elements. Each element in...
A single linked list is a way to store a collection of elements. Each element in a linked list is stored in the form of a node. Draw a diagram which shows a traversal algorithm in a single linked list to sum up FOUR (4) numbers: 6, -4, -2 and 20. Use the details to assist with your diagram: Show initial state Assign a proper variable for the addition operation. Show the steps by circling the current node.
Test each algorithm (Counting Sort, Radix Sort, and Bucket Sort algorithms) on three different arrays of...
Test each algorithm (Counting Sort, Radix Sort, and Bucket Sort algorithms) on three different arrays of 1000 elements each with the following properties: By the way: To perform bucket sort the right way, convert the array elements to a value between 0 and 1 Array1: integers only in the range 0 through 999, already sorted in increasing order Array2: integers only in the range 0 through 999, already sorted in decreasing order Array3: integers only in the range 0 through...