Vector is an ordered set of elements that is also called dynamic array. It is si

Question

Vector is an ordered set of elements that is also called dynamic array. It is similar to

the list data structure that you learned in the data structure course, except that the

data is saved in order (not sorted). You need to implement the Vector ADT using

C++ class (prototype is provided by the instructor). You need to download the

Vector.h file from the ecourses, and implement all functions defined in the class

using C++ with a file named Vector.cpp. You will also need to create a Main.cpp to

create object(s) of the Vector class, and test if these functions are working correctly.

The following is the list of functions defined in Vector ADT.

• append(element) - Add a new element to the end of the collection.

• clear() - Make the collection empty.

• contains(element) - Does the collection contain the given element?

• elementAt(index) - Access the element at the given index.

• isEmpty() - Is the collection empty?

• isFull() – Is the collection full?

• removeAt(index) - Remove the element at the given index.

• getSize() - How many elements are in the collection?

In addition, the following two functions are bonus if you have time to complete them.

You need to uncomment them in the header file.

• insertAt(index, element) - Insert a new element at the given index.

• remove(element) - Remove the given element from the collection.

Explanation / Answer

Linked list is one of the fundamental data structures in C.

Knowledge of linked lists is must for C programmers. This article explains the fundamentals of C linked list with an example C program.

Linked list is a dynamic data structure whose length can be increased or decreased at run time.

How Linked lists are different from arrays? Consider the following points :

When to prefer linked lists over arrays? Linked lists are preferred mostly when you don’t know the volume of data to be stored. For example, In an employee management system, one cannot use arrays as they are of fixed length while any number of new employees can join. In scenarios like these, linked lists (or other dynamic data structures) are used as their capacity can be increased (or decreased) at run time (as an when required).

How linked lists are arranged in memory?

Linked list basically consists of memory blocks that are located at random memory locations. Now, one would ask how are they connected or how they can be traversed? Well, they are connected through pointers. Usually a block in a linked list is represented through a structure like this :

So as you can see here, this structure contains a value ‘val’ and a pointer to a structure of same type. The value ‘val’ can be any value (depending upon the data that the linked list is holding) while the pointer ‘next’ contains the address of next block of this linked list. So linked list traversal is made possible through these ‘next’ pointers that contain address of the next node. The ‘next’ pointer of the last node (or for a single node linked list) would contain a NULL.

How a node is created?

A node is created by allocating memory to a structure (as shown in above point) in the following way :

So, as we can see above, the pointer ‘ptr’ now contains address of a newly created node. If the linked list is empty and first node is created then it is also known as head node.

Once a node is created, then it can be assigned the value (that it is created to hold) and its next pointer is assigned the address of next node. If no next node exists (or if its the last node) then as already discussed, a NULL is assigned. This can be done in following way :

How to search a node in a linked list?

Searching a node means finding the node that contains the value being searched. This is in fact a very simple task if we talk about linear search (Note that there can be many search algorithms). One just needs to start with the first node and then compare the value which is being searched with the value contained in this node. If the value does not match then through the ‘next’ pointer (which contains the address of next node) the next node is accessed and same value comparison is done there. The search goes on until last node is accessed or node is found whose value is equal to the value being searched. A code snippet for this may look like :

How a node is deleted?

A node is deleted by first finding it in the linked list and then calling free() on the pointer containing its address. If the deleted node is any node other than the first and last node then the ‘next’ pointer of the node previous to the deleted node needs to be pointed to the address of the node that is just after the deleted node. Its just like if a person breaks away from a human chain then the two persons (between whom the person was) needs to join hand together to maintain the chain.

A Practical C Linked List Example

Here is a practical example that creates a linked list, adds some nodes to it, searches and deletes nodes from it.

In the code above :

Also, as you see from the above Linked list example, it also uses pointers. If you are new to C programming, you should understand the fundamentals of C pointers.

The output of the above code looks like :

Related Questions

Navigate

• Browse (All)
• Browse V
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.