Comparison between Array, Linked List and Vector

Arrays, linked lists and vectors are used as a storage for multiple element components. Each of these has its own merits and demerits in terms of memory occupied, speed of traversal and complexity. In this post, we will try to have a brief but concise comparison between the three:

Array : Array is a data structure that can store a fixed number of elements of of similar type at contiguous memory locations.

In C, the most simple way to declare an array is as shown below:

int a[10];

Figure 1: Storage of array elements

This statement will create an array of 10 integer elements located at contiguous locations as can be seen in figure 1 alongside. Let us say, first element is located at 100th location in memory; then, second element will be at 104th location assuming the size of integer as 4 (although size of integer depends on machine. On 64 bit machine, size of integer will be 8 byte ) and third element will be located at  108 and so on.

NOTE: The given example of storage of array in memory does not represent real memory locations. This is just for the sake of understanding. 

Since, array elements are located at contiguous memory locations, rate to access any element in array is constant O(1). e.g. nth element can be accessed as :

    base address + (n-1)*size of element

e.g. 3rd element is present at 100 + 2*4 = 108th address.

Advantages of array : As explained, array has high access rate of order O(1) i.e. constant access rate. The access time for a very large array can be reasonably small.

Disadvantages : 1) Since size of array is constant. It has to be pre-determined, as that much amount of memory has to be reserved which has to be contiguous locations, which can lead to memory wastage.

2) If memory is fragmented into smaller chunks then array creation may fail, because array elements are stored at contiguous locations. e.g. let us say, there is a space of 1024 bytes in memory but memory is fragmented into 2 chunks of 512 bytes. Then, maximum size allowed of an array will be 512 although total available space is 1024 bytes. 

3) Insertion and deletion in the middle of array is a costly operation because elements to the right of required position has to be moved. 

Linked List : Due to the disadvantages of array related to insertion and deletion time, Linked list came into existence. Linked list is a linear data structure that can store collection of data elements. Number of elements to be stored in linked list need not to be constant. It can be dynamic. Elements in linked list need not to be stored at contiguous locations. Since, elements are not kept at contiguous locations, each element contain the location (address) of next element.

Hence, data elements in Linked list consist of two parts:

1. Data and
2. Address of next element. 

The structure representing an element in a linked list can be defined in C as shown below

struct link_list {    int data;    struct link_list *next; }; 

Figure 2: Linked list representation

Advantages of Linked List : 1) Size of linked list need not to be constant. It can be dynamically decided at the run time.
2) Insertion and deletion in the middle of linked list is of order of 1, O(1) i.e it is constant. It just requires changing the pointers.e.g If you want to add an element  at 3rd position i.e. after 200, 2nd node will point to location 250 instead of 300 and new location 250 will point to 300.

Disadvantages : 1) Access rate is lesser than that of array. Complexity of accessing element is of order of n O(n) where n is number of elements in linked list because one has to traverse through all the element to access last element.
2) Extra memory cost. An element in a list does not contain only data, but pointer to next element as well.   If data is some huge object say 128 bytes, then pointer of size 4 bytes is not a big overhead but if the data is itself of size 4 bytes like an integer then size of each element will be doubled.

Vector : Vector is a data structure which provides advantages of both linked list and array. Major advantage of array is higher access rate and that of linked list is dynamic size. A vector is a hybrid of these two. 

Vector data structure internally uses an array of some user defined size let us say N. When the user tries to put N+1th element in vector following operations takes place:

1.   It internally creates a new array of double size i.e. 2N 
2.  Copies the element of previous array into newer one, 
3.  Destroy the previous array 
4.  New array comes in place of previous one. 

From this, we can see that extending size of vector is a heavy operation. Hence there is always a trade off between speed and memory. Because, if you choose smaller size initially; then, you are making sure that memory is not wasted. But as soon as your size reaches threshold and new element is to be inserted, above described operation takes place which slows down your activity. On the other hand, if you choose initially larger size, one can get rid of above operations. But then, memory may get wasted. In such cases where we over-estimate size, there is no difference between an array of max size and vector.

So, its a tricky part to choose initial size of vector. You have to choose wisely which depends upon application to application.If you don't mention the size of vector while construction then compiler chooses a default size that I guess depend upon library implementation.

There are so many other linear data structures like skip list, deque etc that tries to optimize the performance and tries to make use of advantages provided by linked list and array.

Also read:

• Problem - can you figure out is there something wrong with this code
• Binary decision diagram
• Can pure virtual functions be defined as well?
• Dead reference problem and its detection
• Automatic include of header dependencies in makefile

Noise margins

In this realistic world, nothing is ideal. A signal travelling along a wire/cable/transmission line is susceptible to noise from the surroundings. Also, there is degradation in signal due to parasitic elements involved in the line. Moreover, the output signal produced by the transmitter itself only does resemble the ideal signal thereby worsening the scenario. There are repeaters/buffers along the line to minimize the impact of noise. But there is a limit up to which degradation is allowed beyond which the receiver is unable to sense the correct value of the signal. This degradation is measured in terms of noise margins. One can find the topic discussed in all the textbooks related to digital logic and system design might it be CMOS, TTL or any other logic family.

Let us illustrate the concept of noise margins with the help of an example. Let us assume that a signal has to travel from a transmitter to a receiver through an inter-connect element (or, commonly called as a net) which will only degrade the signal, since there is no active element in-between transmitter and receiver. The output signal produced by Transmitter (Tx) will deviate from ideal voltage levels as is shown in figures 1 and 2 for logic level ‘1’. In addition, there will be signal degradation by inter-connect element as well as noise induced from the surroundings. As a result, the band of voltages that can be present at the receiver input for logic ‘1’ will further widen. Now, there are two cases:

1. If the band voltages recognized as logic ‘1’ by the receiver is super-set of the band of voltages that can exist at the receiver input as shown in figure 1, receiver will recognize the transmitted logic ‘1’ for all the cases. This is the desired scenario as no logic ‘1’ transmitted will be missed by the receiver. This scenario is depicted in figure 1, wherein the noise induced by surroundings is such that the range of voltages present at the receiver does not violate the band of voltages recognized as voltage '1' by the receiver. So, it will be recognized correctly as logic '1' by the receiver.

Figure 1: Figure showing the noise induced is less than noise margin

2)  If the band of values recognized as logic ‘1’ by the receiver is a sub-set of the band of voltages that can exist at the receiver input as shown in figure 2, there will be some cases that will not be recognized as logic ‘1’, but are intended to be recognized. So, there will be a loss of information/incorrect transmission of information possible in such cases. This scenario is depicted in figure 2, wherein the noise induced by surroundings makes the band of voltage at the receiver's input larger than that can be decoded correctly as logic '1' by the receiver. So, there is no guarantee that the signal will be perceived as logic '1' by the receiver.

Figure 2: Figure showing the noise induced is greater than noise margin

Let us now label each of these regions to make the discussion more meaningful. The lowest voltage that will be produced as logic ‘1’ by the transmitter is termed as VOH and, let us say, highest is VDD. (We are here considered about lower level only). So, the range of voltages produced by the transmitter is (VDD – VOH).  And let the receiver accept voltages higher than VIH. So the range of voltages accepted by the receiver will be (VDD – VIH). So, the maximum degradation that can happen over the communication channel is (VOH – VIH) which is nothing but the noise margin. If the degradation is less than this figure, the logic ‘1’ will be recognized correctly by the receiver; otherwise it won’t. So, the noise margin equation can be given as below for logic '1':

Noise margin for logic '1' (NM) = VOH – VIH

Where

VOH = Lowest level of voltage that can be produced as logic '1' by the transmitter

VIH = Lowest level of voltage that can be recognized as logic '1' by the receiver

Similarly, for logic ‘0’, the range of outputs that can be produced by the transmitter is (0 - VOL) and the range of input voltages that can be detected by the receiver is (0 – VIL), thereby providing the noise margin as:

Noise margin (NM) = VIL – VOL

Where

VIL = Highest level of voltage that can be recognized as logic ‘0’ by the receiver.

VIH = Highest level of voltage that is produced as logic ‘0’ by the transmitter.

Figure 3 shows all these levels for the example we had taken earlier to demonstrate the concept of noise margins.

Figure 3: Noise margin

From out preceding discussion, if the degradation over the communication channel is more than noise margin, it will not be detected correctly by the receiver. So, it is imperative for the designer to design accordingly.

Definition of noise margin: Thus, we can conclude this post by defining noise margin as below:

"Noise margin is the difference between the worst signal voltage produced by the transmitter and the worst signal that can be detected by receiver."

Also read: 

• Latchup in CMOS devices
• Metal ECO - the process
• Regions of operation of MOS transistors
• False paths - what are they
• Latency and throughput - the two measures of system performance