Linked Lists using C++

Submitted by: 
Language: 

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.


Add new comment

Filtered HTML

  • Web page addresses and e-mail addresses turn into links automatically.
  • You may insert videos with [video:URL]
  • Allowed HTML tags: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd> <table> <tr> <td> <th> <img> <h1> <h2> <h3> <iframe> [video]
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>, <asp>, <c>, <cpp>, <csharp>, <css>, <html4strict>, <java>, <javascript>, <mysql>, <php>, <python>, <sql>, <vb>, <vbnet>. The supported tag styles are: <foo>, [foo].
  • Lines and paragraphs break automatically.

Plain text

  • No HTML tags allowed.
  • Lines and paragraphs break automatically.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.