16 replies to this topic

[Melchoire]

I hear linked-lists are really important data structures that are used a lot. From my understanding they're a group of nodes carrying a piece of data and each is connected to another one. And then there's the singly, doubly and multi linked lists and shit. So what kind of significance do they hold then?

I wanna have a little variety with my portfolio so I was gonna have a go at writing a linked list in C++. Anyone wanna help me out with articles/how to's or even just an explanation....

[Noitidart]

Hmm from the sound of the name I would think its something like javascript objects.

[Tsunade]

Your mom is so fat she sat on a binary tree and turned it into a linked list in constant time

[Faval]

Linked lists are basically like an object that has a pointer to another object until it reaches the last object that has something like a null value for the pointer.

Think of it as something like an array except instead of an index, it's a pointer and instead of going directly to any point in the array with the index...you have to traverse it step by step to reach it.

I would just google pointers/linked list c++ and you should find stuff for it.

[Noitidart]

Oh so like pass by reference faval?

lol tsu you're crazy

[Warlord.]

In a linked list, each node is an instance of a class representing what you want to store.

In a singly-linked list, each node generally has getNext/set methods and a reference to the next node.

In a doubly-linked list, each node has standard methods including getNext/getLast and a reference to the previous and next node. This allows you to traverse either way instead of needing to iterate all the way through to go backwards like a singly-linked list.

A multi-linked list can have any number of references from each node, usually based off of organizing a piece of data that each element has.

I haven't done any of these in C++ but did em in Java for school.

[Faval]

Oh so like pass by reference faval?

lol tsu you're crazy

Not at all sadly. Programming linked lists with a cheap c++ compiler is a pain in the rear end until you get the hang of it.

Basically you create your class/struct for the linked lists.

A simple struct would be like this:

	struct node
	{
		string name;
		int value; //<variables you want the node to have>
		node *next; //<- this is the pointer, you can have more for a double linked list and multi-linked list for the double linked list you would have a node *previous
	};

	node *start_pointer = NULL;   
	node *temp = new node;
	node *temp2 = new node;

	// too lazy to write prompts for these things
	temp->name = "pie";
	temp->value = 1;
	temp->next = NULL;

	//add to the end of starting pointer
	if( start_pointer->next == NULL)
        start_pointer = temp;
	else
	{ 
   	// the list isn't empty so we have to traverse it to the end and then add it there.
		temp2 = start_pointer;
		while (temp2->next != NULL)
		{  
			temp2 = temp2->next;
			// Move to next link in chain
		}
		temp2->next = temp;
	}

It can be complicated sometimes...especially when you go into deleting nodes along double/multi linked lists so it's probably better to go out and research.

Edit - Curses my formatting doesn't show up.

Edited by Faval, 29 October 2010 - 05:39 AM.

[Melchoire]

K so going only by the few things I learned after skimming wikipedia i came up with this function for adding nodes.

void LLIST::addNode(int index, int val)

{

	Link *newNode = new Link;

	newNode->value = val;



	Link *temp = new Link;

	temp = Head;



	Link *curr = new Link;



	int i = 0;



	while(i < index)

	{

		curr = temp->Next;

		i++;

	}

	//curr is now in the position before the node that will be pushed



	temp = curr;

	curr->Next = newNode;

	newNode->Next = temp->Next->Next;



	size++;

}

I'm pretty sure I'm handling everything else properly; with the pointers and what not. The codex executes but the program just freezes and becomes unresponsive...

[Faval]

K so going only by the few things I learned after skimming wikipedia i came up with this function for adding nodes.

void LLIST::addNode(int index, int val)
{
	Link *newNode = new Link;
	newNode->value = val;

	Link *temp = new Link;
	temp = Head;

	Link *curr = new Link;

	int i = 0;

	while(i < index)
	{
		curr = temp->Next;
		i++;
	}
	//curr is now in the position before the node that will be pushed

	temp = curr;
	curr->Next = newNode;
	newNode->Next = temp->Next->Next;

	size++;
}

I'm pretty sure I'm handling everything else properly; with the pointers and what not. The codex executes but the program just freezes and becomes unresponsive...

You didn't set curr to anything other than a new node. The next is therefore pointing to NULL so it freezes/crashes.

Also why are you making a new newNode and then setting the value of it in the function? What's the point of the loop if you're just going to make a new one? It's probably better to pass the node and a value to the function. The index seems pointless(pun intended) to me but maybe I'm not seeing the whole program here.

So you have to write curr = newNode before the loop.

Edited by Faval, 29 October 2010 - 05:44 AM.

[Melchoire]

You didn't set curr to anything other than a new node. The next is therefore pointing to NULL so it freezes/crashes.

Also why are you making a new newNode and then setting the value of it in the function? What's the point of the loop if you're just going to make a new one? It's probably better to pass the node and a value to the function. The index seems pointless(pun intended) to me but maybe I'm not seeing the whole program here.

So you have to write curr = newNode before the loop.

Ah fuck >_< I switched the curr and temp around so curr was supposed to be set to the "head" of the list, not temp. I'll fix that, thanks =]

The function adds a new node at a specified position with a specified value. It should really be called "insertNode". The loop transverses the list until the index is met; then the node at the specified position gets pushed forward and replaced by "newNode".

I think I can make it more efficient if I use "Link" as the parameter instead of index and val. Is there anything else you see wrong with it?

[Faval]

Ah fuck >_< I switched the curr and temp around so curr was supposed to be set to the "head" of the list, not temp. I'll fix that, thanks =]

The function adds a new node at a specified position with a specified value. It should really be called "insertNode". The loop transverses the list until the index is met; then the node at the specified position gets pushed forward and replaced by "newNode".

I think I can make it more efficient if I use "Link" as the parameter instead of index and val. Is there anything else you see wrong with it?

Yeah the only reason I can think of why it would crash at that part is because the temp is set to the head and the next of that is a one up on what i is right now. Then again how are you counting the size by the way? Also let's say there are 4 nodes in your linked list and you want to insert something between the 3rd and 4th node. You would want the index to be 2 since you have i = 0.

Actually I take back what I said about using the index and the value as parameters. I didn't notice you were keeping track of the size of your linked list. It's fine to pass the index and value then. If you didn't pass the index, then you wouldn't know where to add the node other than at the end

This sounds like a homework assignment of some sort because I can't imagine why it would matter what the order of items is for singled linked lists. The efficiency of traversing through a linked list is always going to be O(n) and it would be more efficient to use a hash table/binary tree if you wanted to properly index items.

Edited by Faval, 29 October 2010 - 07:13 AM.

[Melchoire]

Yeah the only reason I can think of why it would crash at that part is because the temp is set to the head and the next of that is a one up on what i is right now. Then again how are you counting the size by the way? Also let's say there are 4 nodes in your linked list and you want to insert something between the 3rd and 4th node. You would want the index to be 2 since you have i = 0.

Actually I take back what I said about using the index and the value as parameters. I didn't notice you were keeping track of the size of your linked list. It's fine to pass the index and value then. If you didn't pass the index, then you wouldn't know where to add the node other than at the end

This sounds like a homework assignment of some sort because I can't imagine why it would matter what the order of items is for singled linked lists. The efficiency of traversing through a linked list is always going to be O(n) and it would be more efficient to use a hash table/binary tree if you wanted to properly index items.

Actually this is gonna be a sample program for a portfolio I'm making. I'm one of the best programmers in 2nd year but I want the employers to actually see what I'm capable of, hence the portfiolio.

Could you elaborate further on hash tables and binary trees? Tbh, I don't even know what a linked list could be used for

[Faval]

Actually this is gonna be a sample program for a portfolio I'm making. I'm one of the best programmers in 2nd year but I want the employers to actually see what I'm capable of, hence the portfiolio.

Could you elaborate further on hash tables and binary trees? Tbh, I don't even know what a linked list could be used for

Hmmm, you'll definitely get to classes that teach you about hash tables and binary trees, especially trees since that's all the rage for classes.

In it's basic form a hash table is a table with a Key and a Value. Hmm there's a lot to cover on this and I hardly remember much of it. I've only used it for a few things.

Binary search trees are like linked lists in a way but structured differently and is always in order. It's somewhat difficult to explain so I'll try to explain it. You have the parent node, the one that's on the top and it has a left and right pointer but for trees, we call them children The left child of the parent node will always have a value less than the parent while the right will always have a value greater than the parent...hmm this could be a long explanation but you can see an example of how the tree looks and works here - Wiki BST. If you need to ask anything specific feel free.

Regarding your future employer prospects, I think you should look into what kind of job you want, look at the job postings and see what skills they desire. Obviously you're not going to have all the required skills and they don't expect that either but if you have a strong understanding of the main things they want then you're good.

[EmperoR]

Why would you use linked-list? The only advantage is space-efficiency.

[alphadark]

I hate pointer... i get soo many errors while using them

[Melchoire]

I hate pointer... i get soo many errors while using them

I hate them too. They confuse the fuck out of me. But I want to master them =P

[pyke]

Why would you use linked-list? The only advantage is space-efficiency.

We had to use them (my class) a lot in C, I prefer arrays, but a doubly linked list is pretty handy.