From basic English, we are aware of the difference between linear and non-linear. In simple terms, linear means straight, and non-linear mean the opposite i.e. not straight. Similarly, data structures are divided into linear and non-linear.
Linear Data Structure:
The data elements are arranged in a linear order where each and every element is attached to its previous and adjacent element. Only a single level is involved and all the elements can be accessed in a single run only. The implementation is simple compared to Non-Linear Data Structure.
Example: Arrays, Stack, Queue, Linked List, etc.
Non-Linear Data Structure:
The data elements are usually arranged in a hierarchical order. It involves multiple levels and all the elements cannot be accessed in a single run. The complexity of implementation is higher compared to the linear data structure.
Example: Trees, Graphs, etc.
Arrays:
It is a collection of data elements that are stored at contiguous memory locations. It is used to store data of the same type. The elements in an array can be accessed using the count of the position where the element is. This position is known as an index.
Representation of array: [ ] (square braces)
Declaration of an array: A [s] where A is the name of the array and s is the size of the array.
Initialization of an array:
A [ ]={1,2,3,4,5}; A is an array of size 5.
Note: Even if the size is declared 10, elements can be filled up to 10 but not >10.
Accessing the elements of an array:
A [i] gives the value at index i in the array.
Note: In general, the indices start from 0 when implementing in any programming language.
A [0] = 1; A [2] = 3 and so on. Elements can be randomly accessed from any location of the array. All the elements can be displayed by running a loop till the end of the array i.e. size of the array.
Advantages:
- Arrays provide random access to the elements which increases the speed of access.
- Arrays are used to represent elements of the same data type under the same name, i.e. name of the array.
Disadvantages:
- The size of the array cannot be changed once declared i.e. memory allocation is static.
- Basic operations such as insertion and deletion are complex on arrays as each element has to shift its position after performing the operation.
Arrays are used in the implementation of stacks, queues, Heap, and many sorting and searching algorithms.
This is a basic introduction to arrays to make Linked List a little easier to understand. Now overcoming the disadvantages of arrays, here comes our next discussion, Linked Lists.
Linked List:
Unlike arrays, linked lists are linear data structures where the elements are not stored in contiguous memory locations. It is a sequence of nodes that are connected to each other via pointers to the address of the node. The structure of a linked list is as follows:
Null: The last node of the list points to null indicating the end of the list.
Node: It is used to store the data and address of the next node.
Data: It is the value stored in the node.
Next: It stores or points to the location of the next node and is useful while traversing or performing operations on the linked list.
It is called a Linked List as all the nodes are connected via a pointer i.e. next.
Operations on Linked List:
Insertion:
Step 1: Assuming that a linked list has been created, node D has to be inserted between A and B. Search through the linked list and find out the position where the node has to be inserted.
Step 2: Link the ‘next’ of node D (node to be inserted) to the adjacent node where the node has to be inserted, here B.
Step 3: Remove the link between node A and node B and make the pointer ‘next’ to point to node D. The insertion is completed!
Why Step 3 should not be done at Step 2? Or can step 2 and step 3 be interchanged? (Answer explained with respect to the above example)
The answer is no! If the link between node A and node B is removed first, we cannot find the node B in the memory as the linked list is not stored in contiguous memory locations. If we maintain the link between A and B and make a link between node D (new node), the balance will be maintained.
You will more understand if you actually implement. You may get a garbage value when performing other operations on the linked list after insertion without following the correct order.
Deletion:
Step 1: Assuming the linked list has been created and it is non-empty, find the node to be deleted through sequential search or any other algorithm. Here we wish to delete the node B.
Step 2: Make the ‘next’ of the node previous (D) to the node to be deleted (B) point to node next (C) to the node to be deleted (B). Make D point to C.
Step 3: Delete the link between node B and node C. Yep, we are done with the deletion.
The answer remains the same as above if you think of interchanging step 2 and step 3.
Reversing the linked list:
Reversing doesn’t mean printing the list in reverse order 😅! I used to do the same with my assignments! So, let’s reverse.
Step 1: Make the last node of the list to its preceding node. Do the same with all the nodes except for the first node as we don’t have any node before that. After this process, the last node C becomes the first, and node A becomes the last. But we aren’t done.
Step 2: We know that the head points to the first node and the last node points to null. So, point head to the node C and point node A to null. So, we are done with reversing the linked list as well!
Can the head directly pointed to the last node at first? (Answer explained with respect to the above example)
The answer still comes no! If you make the head point to the last node at first, how will we know that A is the first node and it has to point to null? Hence, we remove null at the first and make necessary changes for the head at the last.
Advantages:
- They are dynamic in nature which allocates the memory when required, during the time of execution, unlike array which is static.
- Insertion and deletion operations are simple compared to arrays.
- Stacks and Queues can be implemented easily.
- Insertion and deletion operations can be performed on the list in constant time.
Disadvantages:
- Extra memory is consumed as pointers are required to be stored.
- Implementation of reverse traversal is complex in linked lists.
- Elements cannot be accessed randomly and should be accessed sequentially.
Applications:
- Implementation of stacks, queues, graphs, and trees.
- Used for polynomial representation
- Implementation of hash tables.
Techprodezza 