Arrays vs. Linked Lists

Difference Between Arrays and Linked Lists

The arrays are the data structures that are most commonly used to preserve the collection of items. Most programming languages ​​provide methods that easily declare arrays and elements of the access in arrays. Linked list, the list more accurately called singly-linked list, is a data structure that can be used to store collection of items. It consists of a sequence of nodes and each node has a reference to the next node in sequence.

An important property of an array is ​​that a single block of memory is allocated to an entire array and the array gives each item its own space. Once an array is ​​defined, its size is fixed. So if you are unsure of the size of the array at compile time, you should define an array large enough to be on the safe side. But mostly we really use less number of elements than we have allocated. So a considerable amount of memory is really wasted. On the other hand if the ‘rather large array” is not really big enough, the program would crash.

A linked list allocates memory connected to its elements separately in its own block of memory and the general structure is obtained by connecting these elements as links in a chain. Each item in a linked list is connected to two fields. The data field holds the actual data stored and the next field has the reference to the next item in the chain. The first element of linked list is kept as the head of the linked list.

Each component retains its data and all elements except the last one keep a reference to the next item. The value of last element is null in the next field. Any item in the list can be accessed starting at the head and following the successive pointer till you meet the desired item.

Although linked lists and arrays are related and are similar in the sense that both are used to store the collection of items, they are different due to the strategies they use to allocate memory for its elements. Arrays allocate memory for all its elements as a single block and the size of the array must be determined at runtime. This would make arrays poorly efficient in situations where you do not know the size of the array at compile time. Since a linked list allocates memory to its elements separately, it would be much effective in situations where you do not know that the dimensions of the list at compile time. The declaring and assessment of items in a linked list are not as easy and simple when compared to the direct approach of the elements in an array using its indices.

 

Category: VS  |  Tags: