• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本 扫码下载译学馆APP

#### 数据结构：#4 数组vs链表

Data Structures: Arrays vs Linked Lists

In our previous lesson, we introduced you to linked list data structure

and we saw how linked lists solve some of the problems that we have with arrays.

So now the obvious question would be which one is better – an array or a linked list.

Well, there is no such thing as one data structure is better than another data structure.

One data structure may be really good for one kind of requirement,

while another data structure can be really good for another kind of requirement.

So, it all depends upon factor like what is the most frequent operation that you want

to perform with the data structure or what is the size of the data

and there can be other factors as well.

So, in this lesson, we will compare these two data structures based on some parameters,

based on the cost of operations that we have with these data structures.

So, all in all we will comparatively study the advantages and disadvantages and try to

understand in which scenario we should use an array

and in which scenario we should use a linked list.

So, I will draw two columns here, one for array and another for linked list

and the first parameter that we want to talk about is the cost of accessing an element.

Irrespective of the size of an array

it takes constant time to access an element in the array.

This is because an array is stored as one contiguous block of memory.

So, if we know the starting address or the base address of this block of memory.

Let us say what we have here is an integer array and base address is 200.

The first byte in this array is at address 200.

Then let’s say if we want to calculate the address of element at index i,

then it will be equal to 200 plus i into size of an integer in bytes.

So, size of an integer in bytes is typically 4 bytes.

So, it will be 200 + 4*i.

So, if 0th element is at address 200

if we want to calculate the address for element

at index 6, it will be 200 plus 6 into 4 which will be equal to 224.

So, knowing address of any element in an array is just this calculation for our application.

In terms of big-oh notation, constant time is also called O(1).

So, accessing an element in an array is O(1) in terms of time complexity.

If you are not aware of big-oh notation

check the description of this video for a tutorial on time complexity analysis.

Now, in a linked list, data is not stored in a contiguous block of memory.

So, if we have a linked list something like this, let’s say we have a linked list of integers here,

then we have multiple blocks of memory at different addresses.

Each block in the linked list is called a node and each node has two fields,

one to store the data and one to store the address of the next node.

So, we call the second field, the link field.

The only information that we keep with us about a linked list is the address of the first node

which is also called the head node.

And this is what we keep passing to all the functions also, the address of the head node.

To access an element in the linked list at a particular position

we first need to start at the head node or the first node

then we go to the second node and see the address of the third node.

In the worst case, to access the last element in the list,

we will be traversing all the elements in the list.

In the average case, we will be accessing the middle element may be.

So, if n is the size of the linked list, n is the number of elements in the linked list,

then we will traverse n/2 elements.

So, the time taken in the average case

also is proportional to the number of elements in the linked list.

So, we can say that the time complexity in average case is O(n).

So, on this parameter, cost of accessing an element, array scores heavily over linked list.

So if you have a requirement where you want to access elements in the list all the time,

then definitely array is a better choice.

Now, the second parameter that we want to talk about is

memory requirement or memory usage.

with an array, we need to know the size of the array before creating it,

because arrays is created as one contiguous block of memory.

So, array is of fixed size.

What we typically do is create, we create a large enough array

and some part of the array stores our list

and some part of the array is vacant or empty so that we can add more elements in the list.

For example, we have an array of 7 integers here and we have only 3 integers in the list.

Rest 4 positions are unused.

There would be some garbage value there.

With linked list, lets say we have, let’s say we have this linked list of integers,

there is no unused memory.

We ask memory for one node at a time, so we do not keep any reserved space.

But we use extra memory for pointer variables

and this extra memory requirement for a pointer variable in a linked list can not be ignored.

In a typical architecture let’s say

integer is stored in 4 bytes and pointer variable also takes 4 bytes.

So, if you see, the memory requirement for this array of 7 integers is 28 bytes.

And the memory requirement for this linked list would be 8*3,

where 8 is the size of each node, 4 for integer and 4 bytes for the pointer variable.

So, this is also 24 bytes.

If we add one more element to the list in the array, we will just use one more position,

while in linked list we will create one more node, and will take another 8 bytes,

so this will be 32 bytes.

Linked list would fetch us a lot of advantage if the data, the data part is large in size.

So, in this case, we had a linked list of integers, so integer is only 4 bytes.

What if we had a linked list in which the data part was

some complex type that took 16 bytes.

So, 4 bytes for the link and 16 bytes for the data, each node would have been 20 bytes.
4字节指针 16字节数据 每个结点共20字节
An array of 7 elements for 16 bytes of data would be

16 byte for each element would be 112 bytes.

And linked list of 4 would be only 80 bytes.

So, it all depends.

If the data part of a list takes a lot of memory,

linked list will definitely consume lot less memory.

Otherwise, it depends what strategy we are choosing to decide the size of the array.

At any time how much array are we keep unused.

Now, one more point with memory allocation

because arrays are created as one contiguous block of memory,

sometimes when we may want to create a really really large array, then

maybe memory may not be available as one large block,

but if we are using linked list, memory may be available as multiple small blocks.

So, we will have this problem of fragmentation in the memory.

Sometimes, we may get many small units of memory

but we may not get one large block of memory.

This may be a rare phenomenon, but this is a possibility.

So, this is also where linked list scores.

Because arrays have fixed size, once array gets filled and we need more memory, then

there is no other option than to create a new array of larger size

and copy the content from the previous array into the new array.

So, this is also one cost which is not there with linked list.

So, we need to keep these constraints and these requirements in mind when we want to

decide for one of these data structures for our requirement.

Now, the third parameter that we want to talk about is

cost of inserting an element in the list.

Remember when we are talking about arrays here, we are also talking about

the possible use of array as dynamic list.

So, there can be 3 scenarios in insertion.

First scenario will be when we want to insert an element at the beginning of the list.

Let’s see we want to insert number 3 at the beginning of the list.

In the case of arrays,

we will have to shift each element by one position towards the higher index.

So, the time taken will be proportional to the size of the list.

So, this will be O(n).

Let’s say n is the size of the list.

This will be O(n) in terms of time complexity.

In the case of linked list, inserting a node in the beginning

will mean only creating a new node and adjusting the head pointer and the link of this new node.

So, the time taken will not depend upon the size of the list, it will be constant.

inserting an element at the beginning is O(1) in terms of time complexity.

Inserting an element at end for an array, let’s say we are talking about dynamic array,

a dynamic list in which we create a new array if it gets filled.

If there is space in the array, we just write to the next higher index of the list.

So, it will be constant time.

So, time complexity is O(1) if array is not full.

If array is full, we will have to create a new array and copy all the previous content

into new array which will take O(n) time where n is the size of the list.

In the case of linked list, adding an element, inserting an element at the end will mean

traversing the whole list and then creating a new node and adjusting the links.

So, time taken will be proportional to n.

I will use this color coding for linked list.

Here n is the number of elements in the list.

Now, the third case will be when we want to insert in the middle of the list

at some nth position or may be some ith position.

Again in the case of arrays, we will have to shift elements.

For the average case, we may want to insert at the mid position in the array.

So, will have to shift n/2 where n is the number of elements in the list.

So, the time taken is definitely proprotional to n in average case.

So, complexity will be O(n).

For linked list also we will have to traverse

Even though we will not have any shifting, we will have to traverse till that point and

in the average case, time taken will be proportional to n

and the time complexity will be O(n).

If you see , deleting an element will also have these 3 sceanrios

and the time comeplxity for deleting for these 3 sceanrios will also be the same.

And the final point, the final parameter that I want to talk about

is which one is easy to use and implement.

An array definitely is a lot easier to use.

Linked list implemetation especially in C or C++ is more prone to errors

like segmentation fault and memory leaks.

It takes good care to work with linked lists.

So, this was arrays vs linked lists.

In our next lesson, we will implement linked list in C or C++.

We will get our hands dirty with some real code.

So this is it for this lesson.

Thanks for Watching !