Skip to main content

Linked Lists using C++


Linked Lists using C++

In this tutorial, you will learn
1. Different operations of linked list.
2. Implementation of linked list.
3. Why some of the basic functions are available

What are the different operations in linked list?

Following are the operations linked list is supposed to perform.
1. Traversal:
There must be a way to access the elements of a linked list. In linked list, we have data and a pointer pointing to next element. We start from first element and using the pointer pointing to next element we go to the next element and keep doing it until we reach the desired element.
2. Insertion:
As linked list is a data structure so its task is obviously to store data. You make a function inert which has to insert data.
3. Deletion:
In arrays, deleting data requires a lot of resources. Fortunately, in linked list this can be done by simply changing pointers.

4. Destructor:
Making a destructor of linked list is perhaps mandatory. Because frequently there is need to delete . So to free any space already used by list, it must be freed by destructor.
5. Check empty: Check empty function checks if the linked list is already empty. It has its uses in other functions. E.g. in traversal if linked list is empty, it stops the traversal.

6. Copy Constructor:
Making a copy constructor is difficult for linked list but it is required when you make a function which takes a linked list as input also when you want to return a linked list.

What is implementation of a linked list?

First, we should make a node.

  1.  
  2. struct Node
  3. { int data;
  4. Node*next;
  5. Node()
  6. {next=NULL;}
  7. };

In above program, a data type node is made and it contains data and a self referential pointer which is used to point to the next node in link list. A constructor is made and it gives the pointer null value which will be used while making a new node. E.g. if you add a node at the end then it should not point to anything.
  1.  
  2. class Linklist
  3. {
  4. private:
  5. Node* head;
  6. bool checkempty();
  7. public:
  8. Linklist();
  9. Linklist(const Linklist &L);
  10. void Traverse();
  11. void InsertAtStart(int val);
  12. void RemoveFromStart();
  13. void InsertAtEnd(int val);
  14. void RemoveFromEnd();
  15. ~Linklist();
  16. };

We make a class named as Linklist. A pointer is made which points to the first element of link list. And if we know the address of first location then we can traverse the whole linked list. Another function is also added in private named as bool empty() it returns 1 if linked list is empty and 0 if linked list is not empty then it returns 0.
In public, a constructor is made and this constructor gives the value of head equal to NULL. So if head is equal to NULL then linked list is empty and this must be kept in mind while inserting a node at the beginning. At the end, a destructor is present which must release all the space used by a linked list. Other basic functions usually used in the linked list are also given. First the implementation and concept of these functions must be clear to make further functions.

In next tutorial, the implementation of functions and thus giving insight about linked list will be available and after we know these basics, we will be able to use the features of linked list.

Tags

Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. After downloading it, you will need a program like Winzip to decompress it.

Virus note: All files are scanned once-a-day by SourceCodester.com for viruses, but new viruses come out every day, so no prevention program can catch 100% of them.

FOR YOUR OWN SAFETY, PLEASE:

1. Re-scan downloaded files using your personal virus checker before using it.
2. NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.

Add new comment

CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.