Tech Guide Blog

Hey, back to programming again in data structure. It’s now about Linked List, a linear single linked list it’s about to be explained in this post. We can imagine this like a chain, every data has a link to another data. Single Linked List is different from array. In array, we can only insert a new data to the last index after the last data. We can not insert at any place we want. So, the linked list was made.

The Node

At linked list, we add a header, we called it node. This node is used for data to be linked to another data. It’s like each one person has one another person’s address. So, this is the advantage to use linked list instead of array. If a new data want to be placed between another data, we just have to change the address/ node of the data.

Insert data

Feel confused? Let’s get to the code. I will make a simple linear single linked list that can insert a data at any index.

//====START====//

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

class node
{
private:
 int data;
 node * next;
public:
 node()
 {
  next=NULL;
 }
  int get()
 {
  return data;
 }
 void set(int x)
 {
  data=x;
 }
 node * nget()
 {
  return (next);
 }
 void nset(node * nextnode)
 {
  next=nextnode;
 }
};

class Link
{
private:
 node * head, * tail;
public:
 Link()
 {
  head=NULL;
  tail=NULL;
 }
 void add(int data)
 {
  node * baru;
  baru=new node;
  baru->set(data);
  if(!head)
  {
   head=baru;
   tail=head;
  }
  else
  {
   tail->nset(baru);
   tail=baru;
  }
 }
 void view()
 {
  node * temp;
  temp=head;
  if(temp)
  {
   while(temp)
   {
    printf("%d",temp->get());
    temp=temp->nget();
   }
  }
 }
 void addmid(int index,int data)
 {
  int i=0;
  node *temp,*ndata;
  temp=head;
  ndata=new node;
  ndata->set(data);
  while(i<index)
  {
   temp=temp->nget();
   i++;
  }
  ndata->nset(temp->nget());
  temp->nset(ndata);
 }

};

//====END====//

It’s done. You can start to implement this code in your main cpp.

Popularity: 33% [?]

Another data structures type is queue. Adding data is the same as stack, it’s called enqueue. The different between stack is queue use “first in first out”. The first data will be kicked out first when you dequeue it (getting data from queue). There are 2 pointers we can use in queue. Head is pointer that point the first data and tail to point the last data. This picture below may help you to understand.

Linear Queue

There are 2 types of queue, linear and circular. A circular queue has a shape like donut, so we can say the queue is connected. The different is at head position, a linear queue has a static head position, and a circular has a dynamic head position every time you do dequeue.

Circular Queue

This time, I will only tell you how to make a linear queue class in header :D, it looks like stack application at previous post, so it’s unnecessary to write the main code.

//============== start of code ==============//
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#define MAX 255

class lqueue
{
private:
	int data[MAX];
	int tail; // linear queue has a static head, assume head = 0
public:
	lqueue()
	{
		tail = 0;
	}
	void enqueue(int value)
	{
		if (!full())
		{
			data[tail] = value;
			tail++;
		}
	}
	int dequeue()
	{
		if (!empty())
		{
			int temp;
			temp = data[head];
			for (int i = 0; i < tail; i++)
			{
				data[i] = data[i+1];
			}
			tail--;
			return temp;
		}
	}
	bool full()
	{
		if (tail == MAX)
			return 1;
		else
			return 0;
	}
	bool empty()
	{
		if (tail == 0)
			return 1;
		else
			return 0;
	}
	void view()
	{
		for (int i = 0; i < tail; i++)
			printf("%d ",data[i]);
		getch();
	}
};
//=============== end of code ===============//

It’s done. I think it should work fine :))

Popularity: 37% [?]

This time I will show you how to make a stack structure class with Visual C++, I do this with Visual C++ 6.0 Enterprise Edition. Just for info, stack is one of data structure types where data is somewhat placed on top of another data (stack). Adding or removing data can be done only on top of stack itself, last in first out. The adding is called push and getting or removing is called pop.
If you want to put a new data, it should be placed like this.

stack illustration

then, if you want to get a data, it should return the last data you put on it (top of stack).

stack illustration

Pop Stack

The third picture is stack after being popped out. Let’s get to the code then, juts make a header file (.h) and start typing. I will make a simple application that can keep integers with stack method.

//============== start of code ==============//
#include <stdio.h>
#include <conio.h>
#include <windows.h>

#define MAX 255

class cstack
{
private:
	int data[MAX]; // this is the place to keep
	int top; // to point the top of the stack
public:
	cstack() // constructor
	{
		top = 0;
	}
	void push(int value)
	{
		if (!full())
		{
			data[top] = value;
			top++;
		}
	}
	int pop()
	{
		if (!empty())
		{
			top--;
			return data[top];
		}
	}
	bool full()
	{
		if (top == MAX)
			return 1;
		else
			return 0;
	}
	bool empty()
	{
		if (top == 0)
			return 1;
		else
			return 0;
	}
	void view() // make a function to view the data
	{
		int i;
		printf("Just another stack data:n");
		for (i = 0; i < top; i++)
			printf("%d ", data[i]);
		getch();
	}
};
//=============== end of code ===============//

After you finished, you can make a C++ source file (.cpp) and can use that stack class that have you made.

//============== start of code ==============//
#include "header.h" // this must be the same place with your header file

void main()
{
	int choice, temp;
	cstack stack;

	do
	{
		system("CLS");
		printf("MENUn1. Pushn2. Popn3. Viewn4. ExitnChoice: ");
		scanf("%d",&choice);
		system("CLS");
		if (choice == 1)
		{
			printf("Value: ");
			scanf("%d",&temp);
			stack.push(temp);
		}
		else if (choice == 2)
			stack.pop();
		else if (choice == 3)
			stack.view();
	}
	while (choice != 4);
}
//=============== end of code ===============//

Save it and compile to try this simple application.

Popularity: 50% [?]