What is a linked list and what are its characteristics?

Data structure is a very vast field. In data structure, today we will define a linked list in data structure. 

         

What is Linked List?

                 

Linked list is a linear data structure which overcomes the limitation of another data structure array.

                        

In the linked list, each element is considered as an object. Unlike array, in Linked list, there is no any contiguous memory structure. Here each element is linked to the next element through a pointer. 

                         

Every element in the linked list is called Node. Each node contains a key and an additional pointer which points to the next element in the list. The initial pinter of the linked list is called head. Here one thing to clear is that head is not another node but a pointer to the first element of the Linked list. The value of Head will be null for an empty Linked List. 

                                    

What are the characteristics of a linked list?

 

Read out below the characteristics of a linked list.

 

1. Dynamic nature:

 

Linked List is dynamic in nature; it means that the list can shrink or grow depending on the data. Due to its dynamic structure it becomes more powerful than arrays. In an array, each data is stored in a contiguous memory location, but Linked List doesn't need this. Each element in the linked list is spread across the memory linked by the pointer of the node. Whenever a new element needs to be added to the linked list, a separate memory is allocated to store the key and the pointer both. Thus linked lists can also be used as the base of a data structure for stacks, queues, etc. 

 

2. Simplified deletion and insertion operations:

 

In Array, insertion and deletion are very tough operations as it needs to shift the entire elements. In cases when an array is full, it requires copying the entire array and paste to a bigger one to fit. 

Unlike the array, the Linked list has easy insertion and deletion operations. Create a node and  can allocate memory for the data which is to be inserted. Adjust the pointer around the node to execute the operation. 

 

1.     Linear Traversal

 

As we know Arrays provide constant access time and also allows random access of the elements. On the contrary, the Linked List provides only linear traversal thus the worst-case runtime could be O(n).

 

In Array, constant access time is allowed, it also allows random access of the elements. On the other hand, a linked list only provides the linear traversal which makes the worst-case run time O(n). A doubly linked list makes it easy to traverse the Linked list backward.

 

2.     Memory Usage

 

Though Linked List takes extra memory for the pointer, it occupies the spaces efficiently. In arrays, in most of the cases allocated memory remains unused. Thus we can say that linked lists use less memory. 

Original Source: https://www.bulbapp.com/u/what-is-a-linked-list-and-what-are-its-characteristics?sharedLink=c12a8435-a69f-488a-b045-5d3e7c9a26c6

Comments

Post a Comment

Popular posts from this blog

Types of trees in the data structure.

Image
  The trees in the data structure demonstrate the relationship between nodes with the parent-child hierarchy. That is why trees in the datastructure are also called hierarchic data structures.  Trees are one of the most popular and easiest ways to simplify the problems and do searching and sorting very fast. Trees are considered as one of the most advanced and strongest data structures. A tree in the  data structure is the representation of a non-linear data structure. Arrays, classes, and connected lists can be implemented using trees. Trees are a combination of different nodes. Each node is attached to the edges to describe the relationship.  What are trees? A tree is a type of non-linear data structure that stores the information in a hierarchical form. The trees in data structures are one of the mature and most efficient. Trees are represented in the form of nodes attached to edges.    Properties of trees:   l   Every tree has a spec...
Read more

What are arrays in data in Data Structure?

Image
  If you want to make your career in the field of programming, then the first thing you have to learn is the basics of arrays. After that only, you could do the array problem solving questions.                Let us know what an array is.   An array is the collection of elements of the same data type stored at contiguous memory locations   What are the uses of an Array ?   An array is a collection of elements of the same data type and its size sequence is fixed. An array is a derived data type. When we want to store a large amount of data , or access or manipulate a large amount of data, then we use arrays. In an Array all elements have the common name. Arrays work on index numbers. The index of an array starts from 0 and ends with size-1. The collection of the same data type where each element has a separate memory location. An array is static and is a part of linear data str...
Read more

What are trees in Data Structure?

Image
What are Trees in Data Structure? Trees are a type of data structure that represents hierarchical data.   Trees are the type of non-linear data structure that consists of nodes. All the nodes of the trees are connected by an edge. In the linear data structure, the complexity of an operation increases with the increasing size of data. However, in tree data structure you can get quick access to the data which is non-linear.   Trees include various types of data structures and algorithms , which makes the task performance easy and efficient.   Terminologies associated with trees in the data structure are:   ·          Node: A node in Data structure contains a value or a key and pointers to its child nodes. ·          Child node: A child node is connected to its parent node. The left child node has a value smaller than the parent node and the right child node has a value larger than...
Read more