Data Structures using C++
Only basic concepts will be discussed in this tutorial. Implementation using codes will be discussed in next tutorial.
In this tutorial, you will learn
1. Advantages of using arrays.
2. Draw backs of arrays.
3. The basic concepts of linked list.
4. Types of Linked List.
5. Linked list vs. Arrays.
6. Creating a linked list using Object Oriented Programming.
What are some advantages of arrays?
As most of you know the basics of C++ programming or programming in general so you all must have used arrays. You must have enjoyed the advantages of arrays but that’s in your subconscious part of brain. You never noticed what arrays are providing you. So to make you aware of those, main advantages are written below.
1. It gives you instant access. In an array of 1000 elements , you can access each element in an instant Example : int Arr ;
cin>>Arr; In above code, you are making an array of 1000 elements and accessing 99th element . You don’t require passing 98th or any other element.
2. If you know the exact amount of data, it takes less space. For each element of an array, you reserve only one memory location. For an array of 1000 elements, 1000 memory locations will be used.
3. It can be used in implementation of other data structures.
What are some draw backs of arrays?
You have been programming at a low level till now where many factors didn’t matter. Even though your computer was doing a hectic job, there were no efficiency expectations from your code. For development of big software, you should be aware of disadvantages of arrays
1. Array has a fixed size. A time will come when your array will be full.
2. The above problem can be catered by creating a bigger array , but again bigger array means more space is required.
3. As array occupies consecutive locations of memory, adding some data in the middle uses a lot of resources. Suppose you have an array of 1000 integers. 900 of the locations are filled. If you want to add an element in the 20th location, the elements from 20th to 900th location will be shifted right by one. Hence, a lot of time is required.
4. Similarly, deleting an item will require the next elements to be shifted back.
What is linked list?
A linked list is a collection of elements (node) and each node consists of two parts.
2. Address (It can be address of next or previous node depending on type).
Basically, you make nodes in a linked list. Each node has a data and usually the address of next node. A node has two parts.
This part holds the useful information. E.g. if you want to save integers, integers come in this part.
Address or Link:
It is used to chain the list. It contains the pointer containing the address of next element.
You join these nodes using the address.
Types of linked list:
Following are some types of linked list.
1. Singly linked list.
2. Doubly linked list.
3. Circular linked list.
Singly linked list will be discussed in detail as it contains the basic concepts. If you learn singly linked list, the rest two are just food for thought.
Linked list vs. Arrays:
Arrays | Linked list
Instant Access |No instant access
Fixed Size |Size can be adjusted
Operations like insertion and deletion
require more time. |Operations like insertion and deletion re require less time
Creating a node in C++:
Basically, to make a node in C++, you have to make a structure or class. Usually structures are made.
Usually a constructor is also present in the node with next pointer initialized to null. And during insertion of new node, it is given a value but all these things are reserved for next tutorial.
These were the basic concepts of linked list. In next tutorials, implementation using C++, basic operations and the actual codes will be discusses.