Linked Lists in 15 Minutes !!!

Linked Lists : Linked lists are special list of some data elements linked to one another.

Each element pointing to the next element. Each element is called a node, which has two parts.

  1. INFO part which stores the information.
  2. POINTER which points to next element.

In singly linked list  nodes have one pointer pointing to the next node.

Doubly linked list nodes have two pointers prev and next. Prev points to the previous node and next node points to the next node in the list.

Advantages :

  1. Linked lists are dynamic data structure : They can grow or shrink during the execution of a program.
  2. Efficient memory utilization.
  3. Insertion and Deletion are easier and efficient.

Disadvantages :

  1. More memory require, if the number of elements are more.
  2. Accessing the data element is time consuming.

Key terms :

  1. Data Fields
  2. Link fields
  3. NULL pointer :  The link field of last node contains NULL.
  4. External Pointer :  it’s a pointer to the very first element.
  5. Empty list : If nodes are not present in lists.  START = NULL.

Representation of linear linked list

struct node
{
 int data;
 struct node *next;
 };
typedef struct node NODE;
NODE *start;

Operation on linked lists :

  1. Creation
  2. Insertion
  3. Deletion
  4. Traversing
  5. Searching
  6. Concatenation
  7. Display

Linked Lists creation and display code :

#include<iostream>
#include<conio.h>

using namespace std;

struct node
{
	int num;
	node *ptr;
};

typedef struct node NODE;

class LinkedList
{
	NODE *first, *head, *temp;
	int count, choice;
	
public :
	void insert();
	void output();
	LinkedList()
	{
		first = NULL;
		count = 0;
		choice = 1;
	}
};

void LinkedList::insert()
{
	while (choice)
	{
		head = new NODE;
		cout << "Enter the data Element" << endl;
		cin >> head->num;

		if (first != NULL)
		{
			temp->ptr = head;
			temp = head;
		}
		else
		{
			first = temp = head;
		}
		cout << " Do you want to continue : Type 1 or 0 " << endl;
		cin >> choice;
	}
}

void LinkedList::output()
{
	temp->ptr = NULL;
	temp = first;

	cout << "Linked Lists Display :: " << endl;

	while (temp != NULL)
	{
		cout << temp->num << endl;
		count++;
		temp = temp->ptr;
	}
	cout << "Number of items in Linked Lists ::  " << count << endl;
}
Advertisements

C++ Crack Code Notes !!!

Constructor initialization lists – C++ provides a way of initializing member variables that allows us to initialize member variables when they are created rather than afterwards. This is done through use of an initialization list.

class Something
{
private:
int m_nValue;
double m_dValue;
int *m_pnValue;

public:
Something() : m_nValue ( 0 ), m_dValue( 0.0 ), m_pnValue( 0 ) // A default constructor
{
}

Something(int nValue, double dValue, int *pnValue) : m_nValue ( nValue ), m_dValue( dValue ), m_pnValue( pnValue ) // A specific constructor
{
}
};

Composition :  

Life Changing Books… Must Read Before Die !!!

Books List :

  1. 7 Habits Of Highly Effective People – by Stephen R. Covey
  2. How to win friends & Influence people – Dale Carnegie
  3. Think and grow rich- Napolean Hill
  4. Awaken the giant within  – Anthony Robbin
  5. The greatest salesman in world –  OG Mandino
  6. Don’t Sweat the Small Stuff – Richard Carlson
  7. Drive – Daniel H. Pink
  8. The Power of Positive thinking – Norman Vincent
  9. As a Man Thinketh – by James Allen
  10. The War of Art by Steven Pressfield
  11. Turning Pro – by Steven Pressfiel
  12. Flow: The Psychology Of Optimal Experience – by Mihaly Csikszentmihaly

Continue….!!!

Linked List in 15 Minute!!

Definition : Linked list is a data structure used for sorting collection of data.

Properties :

  • Successive elements are connected by pointers.
  • Last element points to NULL.
  • Can grow and shrink in size during execution of a program.
  • Can be made just as long as required.
  • Its does not waste memory space.

Linked List Algorithm using C++ :

Heap Sort in 15 minute !

Definition : Heap sort is comparison based sorting algorithm based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

  • A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap.
  • Binary Heap is a Complete Binary Tree, it can be easily represented as array and array based representation is space efficient. If the parent node is stored at index I, the left child can be calculated by  2 * I + 1 and right child by 2 * I + 2.

Heap Sort Algorithm for sorting in increasing order:
1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps until size of heap is greater than 1.

Heap Sort Algorithm

“The only way to do great work is to love what you do" – Steve Jobs