C++ pointers

[mrkhtn]

Hi all, trying to get my head round pointers in C++ but I'm not getting nowhere!
Can anybody pull the following apart and explain each detail...

void push(DT val)
	{
		Node<DT> * temp = new Node<DT>(); //node is a template?right? what else happens?
		temp->data = val; // ?
		temp->next = head; //?
		head = temp; // ?
	}

This is part of stack ADT method named push....I need to change this method to insert as I am attempting to create a set ADT.

Thanks in advance

[mrkhtn]

heres the full file in all its glory:

#pragma once
#include "Node.h"

template <typename DT>
class TemplateSet
{
private:
	Node<DT> * head;
public:

	TemplateSet(void)
	{
		head = NULL;
	}

	~TemplateSet(void)
	{
	}

	void insert(DT val)//change to set ADT
	{
		Node<DT> * temp = new Node<DT>();
		temp->data = val;
		temp->next = head;
		head = temp;
	}
	void erase(DT val)//change to set ADT
	{
		Node<DT> * temp = new Node<DT>();
		temp->data = val;
		temp->next = head;
		head = temp;
	}
	void push(DT val)
	{
		Node<DT> * temp = new Node<DT>();
		temp->data = val;
		temp->next = head;
		head = temp;
	}

	DT pop()
	{
		if (head == NULL)
			throw 999;
		else
		{
			Node<DT> * temp = head;
			DT val = head->data;
			head = head->next;
			delete temp;
			return val;
		}
	}

	int isNotEmpty()
	{
		return (head != NULL);
	}

};

note im attempting to change this to a set ADT ignore the insert and erase

[Disch]

Looks like a linked list.

Linked Lists are ways to store groups of data so that an element can easily be added/removed anywhere in the list. The idea is, each 'Node' contains 2 things:

1) Data (ie, the information you actually want to store in the list)
2) A pointer to the next element in the list.


So if you have 3 elements, A B and C... A's pointer points to B, and B's pointer points to C.

The "head" is the start of the list. IE: the pointer to the first element in the list.

Your push() function is adding a new element to the head of the list:

void push(DT val)
{
    // the goal is to put the 'val' data at the start/head of this linked list.
    // In order to do this, we create a new node for the data to rest in:
    Node<DT> * temp = new Node<DT>();

    // once we have the node 'temp', we put 'val' in it as the data it is to hold:
    temp->data = val;

    // Now we set its pointer to point to the next element in the list.  Since
    // This node is going to be the new head, so the next node is the old head:
    temp->next = head;

    // Set the new head to this node:
    head = temp;
}

Basically... how it works is... head is the first element in the list... head->next is the 2nd, head->next->next is the 3rd, and so on and so on.

[mrkhtn]

Thanks for the detailed reply, very much appreciated! Have you got any ideas of how I would change this push function to a set insert function. I know that a set is an associative container that doesn't contain any duplicates but would a set insert method have the same method declaration as this push function?

[Disch]

You mean you can't have duplicate entries? A linked list is a poor approach, then.

If you want to make sure the entry isn't a duplicate, you'll have to step through the entire list and check every entry to make sure you're not trying to add something that already exists.

[helios]

It's worth pointing out that unless the list is sorted, doing that would nullify the only advantage linked lists have. Changing the list to an efficient set would involve restructuring the class completely.

[mrkhtn]

Yes duplicates entries are a no go. What I need to do is write class declaration for a SET abstract data type (ADT). I need to modify the above example into a SET insert function.

Can the above push function be used as a SET insert function if modified to not accept duplicates?

I then need to create a find, erase functions for a SET.

[mrkhtn]

My intention is to actually modify the above into a SET class but I'm unsure of how I would restructure the class. Can you point out what would need changing and why?

Thanks

[Disch]

To do it inefficiently, you can just search the entire list for duplicates when you add something.

Otherwise, like helios said, you'll pretty much have to recreate the class from scratch. Sets and other ordered containers are usually in the form of a binary tree (look up on wikipedia -- too much to explain in a post). Binary trees are much faster for finding a specific element or seeing if there are duplicates.

[helios]

std::sets, for example, are usually implemented as red-black trees.

[mrkhtn]

Hi, red-black trees are probably the best option. Do you know of any links that contain some source code that I can reuse and modify? Tried google but no joy :(

Thanks again

[mrkhtn]

I've found some source code but looks way to advance for my level of c++

[writetonsharma]

you can keep your list sorted and use some search algo which has good complexity.
edit the insertion function so that it keep the list sorted.
dont make it complex..

one thing you need to take care is linklist memory will not be contiguous, find a way so that you can implement searching. there are ways though.

[helios]

some search algo which has good complexity.

The only search that can be used with lists is linear search, and it has terrible complexity.

[writetonsharma]

you didnt read my last sentence.

there are ways.

[helios]

Okay, name one.

[writetonsharma]

think.

[helios]

Fuck that. Name one way to implement any search other than linear on a linked list or STFU.

[mrkhtn]

Right I've been reading about the binary tree structure and I'm baffled....This is way to complex for me, can you guys can shed some light onto the subject. How would I implement this data structure into a class?

Is there any other data structure that would be suitable for a SET?

and do you know of any good reading on the subject?

[helios]

If you want an efficient set, no. If you just want a set, you could use an unsorted vector, or a sorted list.