Categories

A sample text widget

Etiam pulvinar consectetur dolor sed malesuada. Ut convallis euismod dolor nec pretium. Nunc ut tristique massa.

Nam sodales mi vitae dolor ullamcorper et vulputate enim accumsan. Morbi orci magna, tincidunt vitae molestie nec, molestie at mi. Nulla nulla lorem, suscipit in posuere in, interdum non magna.

What is a linked data structure?

Linked data structures are one of those data structures which hold a critical importance.

What are linked data structures?

– Linked data structures consist of a number of nodes or we can say data records which are linked together by means of links which are nothing but the pointers.
– These nodes or data records are also organized by the references i.e., pointers.
– The links that are used to link the data records are special kind of data types called pointers which can either be compared for equality or can be de-referenced.
– This feature is what that makes the linked data structures liable to be compared with many data structures including arrays and many other data structures for which it is required to perform arithmetic operations on the links or pointers.
– The references to the array elements are actually its indices.
– The data structure shall be considered as a linked data structure until and unless no arithmetic operations are carried out on its indices.
– Linked data structures come with two methods for linking the nodes:
1. Using dynamic allocation and
2. Using array index linking.
– Some of the linked data structures are search trees, linked lists, expression trees and so on.
– All of these linked structures are widely used in programming.
– They simplify the task of search and arranging in complex and large programs.
– They also form the key building blocks for designing effective and efficient algorithms.
– Some examples of such algorithms are set – union find, topological sort and so on.
– It is important to know that objects in a linked list refer to the same object and store data values of similar types.

Problem with Implementing Linked Data Structure

– Tangling up is common problem while implementing a linked data structure.
– Therefore, it is required that you adopt some new debugging skills to operate on them.
– Make sure that you trace the code using diagrams containing linked data structures by hand while writing, understanding and debugging.
– While tracing, if you do not understand what a particular statement does, draw up a fake memory address to be treated like an ordinary integer.

Arrays and Linked Lists

Arrays make use of contiguous allocation and so the memory next to the array memory can be used for other purposes. – This is the reason why a programming language does not allow for arrays which are supposed to change their sizes.
In the case of linked lists, since each node points to the address of the next node, they can be allocated anywhere in the memory.
While declaring an array, it is important to mention its size though this can either get us running out of space or can lead to memory wastage.
The addition and deletion of the elements in a linked list is done at will. The problem here is that the space required and the access time is more.
– In an array you can directly reach the nth element whereas in a linked list n number of pointers or references has to be followed.
– When you remove an element from an array you have to shift all other elements but in the case of linked lists, de-link the element and free the allocated space.
In linked lists, for insertion, a new node is created and a link is introduced from an existing node to this node.

There has always been an argument up on which among the two is better? Actually none of them is better than the other. It all depends up on what you have to do? i.e., search or update and your priority – whether it is space or time?

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>