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 specific root node. A root node can cross e
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 structure.     What are the characteristicsof an array ?   Have a look at some of
Read more

What is Data Structure and Algorithm?

Image
  Data Structure is the method of collecting and organizing data in an organized way. So, that we can perform different types of operations on these data in a very effective way. Data Structure is a way of rendering data elements in terms of some relationship. Data Structure and Algorithm is a process of better organization and storage of data elements. For example, we have some data which has student’s name with Roll no. Like a student named Rohit and his roll number is 26. Here “Rohit” is of String data type and 26 is of integer data type. We can organize these data as a record lie student record, which will have both students’ names abc their roll number on it. Now we can collect and store the student’s record in a database or file as a data structure. For example “Rohit” 26, “Arman”5, “Sushil” 34.                                          If you know about the concepts of Object-Oriented Programming, then you are aware that class also does the same thing as a data structure.
Read more