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.
那么 就是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.
例如 一个大小为7的整型数组 里面只有3个整型变量
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.
其中 8是每个结点的大小 即4字节整数和4字节指针
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,
而链表中 得创建新结点 又需要8个字节
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.
因此 所需时间是常数 与列表大小无关
So, for linked list
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.
因此 数组大小为n 则需要后移n/2个元素
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
till that position and then only we can adjust the links.
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
显然 删除一个元素 也分为3种形式
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 !
In our previous lesson, we introduced you to linked list data structure