Data Structures: Arrays vs Linked Lists

Summary

This lesson compares arrays and linked lists based on their performance and use cases. Arrays provide constant time access but require fixed memory allocation, which can lead to wasted space or fragmentation issues. Linked lists, on the other hand, offer dynamic memory allocation and faster insertions/removals at the cost of slower access times. The choice between them depends on the specific requirements of the task, such as frequent operations and data size.

Takeaways

• 📚 There's no universally superior data structure; the choice between an array and a linked list depends on specific requirements such as operation frequency and data size.
• 🔍 Arrays provide constant time complexity (O(1)) for element access due to their contiguous memory storage, unlike linked lists which have a time complexity of O(n).
• 💾 Arrays require fixed memory allocation upfront, potentially leading to unused memory, while linked lists allocate memory dynamically without reserved space but use extra memory for pointer variables.
• 🔗 Linked lists can be advantageous when dealing with large data elements, as they consume less memory compared to arrays with significant unused space.
• 🧩 Memory fragmentation is less of an issue with linked lists since they can utilize small blocks of memory, unlike arrays that might struggle to find a single large block.
• 🔄 The cost of inserting or deleting elements in arrays is O(n) for operations at the beginning or middle, while linked lists offer O(1) for insertions at the beginning and O(n) for ends or middles.
• 📈 For dynamic arrays, inserting at the end is O(1) if there's space, but requires O(n) time for array resizing and copying if the array is full.
• 🛠 Implementing linked lists can be more complex and error-prone compared to arrays, with potential issues like segmentation faults and memory leaks.
• 📈 The choice between arrays and linked lists should consider factors like ease of use, memory efficiency, and the specific operations that need to be optimized for the application.
• 🔬 The next lesson will involve practical implementation of linked lists in C or C++, providing hands-on experience with the concepts discussed.

Q & A

What is the primary difference between arrays and linked lists?

Arrays store elements in a contiguous block of memory, allowing constant time access to any element, while linked lists store elements in separate blocks, connected by pointers, which results in linear time complexity for accessing elements.

Why might a linked list be preferred over an array in terms of memory usage?

Linked lists are more memory efficient when dealing with large data types because they do not reserve unused memory, unlike arrays which allocate a fixed size and may have unused space.

What is the time complexity for accessing an element in an array?

Accessing an element in an array is O(1), meaning it takes constant time regardless of the array's size.

How does the time complexity for accessing an element in a linked list compare to an array?

Accessing an element in a linked list is O(n), where n is the number of elements in the list, because you may need to traverse the entire list to reach a specific element.

What is the memory requirement difference between an array and a linked list when storing integers?

An array of 7 integers requires 28 bytes (assuming 4 bytes per integer), while a linked list of 3 integer nodes requires 24 bytes (8 bytes per node, with 4 bytes for the integer and 4 bytes for the pointer).

Why might an array be difficult to use when the size of the data elements is large?

When the data elements are large, the memory requirement for an array increases significantly due to the fixed size allocation, which can lead to memory wastage and potential fragmentation issues.

What is the time complexity for inserting an element at the beginning of a list in an array?

Inserting an element at the beginning of an array is O(n) because all existing elements must be shifted to make room for the new element.

How does the time complexity for inserting an element at the beginning of a linked list compare to an array?

Inserting at the beginning of a linked list is O(1) because it only requires the creation of a new node and adjustment of the head pointer and the new node's link.

What are the three scenarios for inserting an element in an array, and what is the time complexity for each?

The three scenarios are: inserting at the beginning (O(n)), inserting at the end if there is space (O(1)), and inserting at the end if the array is full and requires resizing (O(n)).

Which data structure is generally easier to use and implement, and why?

Arrays are generally easier to use and implement because they have a straightforward structure and are less prone to errors like segmentation faults and memory leaks, which can occur with linked lists.

Outlines

00:00

🔍 Comparing Arrays and Linked Lists

This paragraph introduces the comparison between arrays and linked lists, two fundamental data structures. It emphasizes that neither is universally superior, as their suitability depends on specific requirements such as the most frequent operations and the size of the data. The instructor plans to compare these structures based on the cost of operations like accessing elements, memory usage, and the ease of implementation. The discussion starts with the time complexity of accessing elements, highlighting that arrays provide constant time access (O(1)) due to their contiguous memory storage, while linked lists, which do not store data contiguously, require traversing nodes, resulting in an average time complexity of O(n).

05:04

💾 Memory Usage and Allocation in Data Structures

The second paragraph delves into the memory requirements and allocation strategies of arrays and linked lists. Arrays, being of fixed size, may include unused memory slots, leading to potential waste, especially when only a portion of the array is utilized. Conversely, linked lists do not reserve unused memory, allocating space for nodes only as needed. However, they consume extra memory for pointer variables. The paragraph also discusses how linked lists can be advantageous when dealing with large data types due to their node-based structure, which can lead to lower memory consumption compared to arrays. Additionally, it touches on the issue of memory fragmentation, where linked lists can be more efficient as they can utilize small blocks of memory that might be insufficient for a large array.

10:08

⏱ Time Complexity of Insertions in Arrays vs. Linked Lists

The final paragraph focuses on the time complexity associated with inserting elements into arrays and linked lists. It outlines three scenarios for insertion: at the beginning, at the end, and in the middle of the list. For arrays, inserting at the beginning is O(n) due to the need to shift elements, while inserting at the end is O(1) if there's space or O(n) if a new array must be created. Inserting in the middle also takes O(n) time due to the need to shift elements. In contrast, linked lists offer O(1) time complexity for inserting at the beginning due to simple pointer adjustments. However, inserting at the end or in the middle of a linked list requires traversing the list, leading to O(n) time complexity. The paragraph concludes with a brief mention of the ease of use, noting that arrays are generally simpler to use and implement than linked lists, which can be prone to errors like segmentation faults and memory leaks.

Keywords

💡Linked List

A linked list is a linear data structure in which elements are stored in nodes, and each node points to the next node in the sequence. This structure allows for efficient insertion and deletion of elements without the need to shift other elements as in an array. In the video, the comparison between arrays and linked lists is central, highlighting how linked lists solve problems related to dynamic resizing and element access patterns.

💡Array

An array is a data structure that stores a fixed-size sequential collection of elements of the same type. It is a contiguous block of memory locations, each of which stores an element of the array. The video discusses how arrays provide constant-time access to elements via indexing but may require resizing and element shifting for insertions and deletions.

💡Time Complexity

Time complexity in the context of the video refers to the amount of time taken by an algorithm to run, as a function of the length of the input. It's used to compare the efficiency of operations on arrays and linked lists, such as accessing elements, where arrays have O(1) complexity, and linked lists have O(n) complexity on average.

💡Big-O Notation

Big-O notation is a mathematical notation that describes the upper bound of the time complexity or space complexity of an algorithm. The video uses Big-O notation to express the time complexity of operations on arrays and linked lists, such as O(1) for accessing an element in an array and O(n) for accessing an element in a linked list.

💡Memory Allocation

Memory allocation in the video refers to how data structures are allocated in memory. Arrays require a contiguous block of memory, which can lead to wasted space if the array is over-allocated or the need for reallocation if it's under-allocated. Linked lists, on the other hand, allocate memory for nodes as needed, which can be more memory-efficient for certain use cases.

💡Dynamic Array

A dynamic array is an array that can resize itself when necessary. The video explains that dynamic arrays can grow in size, but this growth requires creating a new array and copying the old elements to it, which is an O(n) operation. This is in contrast to linked lists, which can grow dynamically without the need for such copying.

💡Insertion

Insertion in the video refers to the operation of adding an element to a data structure. The video compares the time complexity of inserting elements at the beginning, end, or middle of both arrays and linked lists. For arrays, insertion can be O(n) due to the need to shift elements, while linked lists can have O(1) insertion at the beginning and O(n) at the end or middle.

💡Deletion

Deletion in the video is the operation of removing an element from a data structure. Similar to insertion, deletion in arrays may require shifting elements, leading to O(n) time complexity, while in linked lists, deletion involves adjusting pointers, which also results in O(n) complexity for the end or middle but is O(1) for the head of the list.

💡Memory Fragmentation

Memory fragmentation is a condition where the memory is divided into many small blocks that are too small to be used efficiently. The video mentions that arrays, being contiguous, can suffer from fragmentation if a large block of memory isn't available, whereas linked lists can utilize smaller, non-contiguous blocks of memory.

💡Ease of Use

Ease of use in the video pertains to the simplicity and safety of implementing a data structure. Arrays are generally easier to use and less prone to errors like segmentation faults or memory leaks compared to linked lists, which require careful management of pointers and memory.

Highlights

Comparison between arrays and linked lists based on operation costs.

No single data structure is universally better; it depends on the requirements.

Arrays provide constant time O(1) element access due to contiguous memory storage.

Linked lists require O(n) time to access an element due to non-contiguous memory blocks.

Arrays have fixed size, necessitating pre-determined memory allocation.

Linked lists do not require reserved space and use memory dynamically.

Linked lists use extra memory for pointer variables compared to arrays.

Memory fragmentation is less of an issue with linked lists than with large arrays.

Arrays may require re-allocation and copying when full, which linked lists avoid.

Inserting at the beginning of an array is O(n), while for a linked list it's O(1).

Inserting at the end of an array is O(1) if space is available, O(n) otherwise.

Inserting at the end of a linked list requires traversing the list, taking O(n) time.

Inserting in the middle of an array or linked list takes O(n) time on average.

Deleting elements has similar time complexities for arrays and linked lists.

Arrays are generally easier to use and implement than linked lists.

Linked list implementation can be prone to errors like segmentation faults and memory leaks.

Next lesson will involve implementing linked lists in C or C++.

Transcripts

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 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 he 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 iif 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 than 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 clock 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 if 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.

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 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

may be 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 in 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 soem 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 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, 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 Cor 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 !