Linked List

Linked list use in coding

Page 1 of 1

12 Replies - 1759 Views - Last Post: 15 December 2010 - 10:37 PM Rate Topic: -----

#1 isha_005  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 15-December 10

Linked List

Posted 15 December 2010 - 02:37 PM

Hi
I was going through linked list piece of code . I am unable to understand what the next pointer is actually pointing to . The next node in the list or the head .
when the pointer variable is pointing to -> data i can understand that the next node value .
but when it is pointing temp ->next = head wherever especially next variable is used I am unable to undertsand .what is the head actually the first node of the list .Please help me in this as i simply dont want to memorize the code i want to understand it properly .



    
#include <stdio.h>
#include <stdlib.h>

struct node{
	int data;
	struct node *next;
};

struct node* add(struct node *head, int data){
	struct node *tmp;

	if(head == NULL){
		head=(struct node *)malloc(sizeof(struct node));
		if(head == NULL){
			printf("Error! memory is not available\n");
			exit(0);
		}
		head-> data = data;
		[b]head-> next = head;  /*what does this piece of code mean */[/b]
               [color="#FF0000"][/color]	
            }else{
		tmp = head;
		
		while (tmp-> next != head)
			tmp = tmp-> next;
		tmp-> next = (struct node *)malloc(sizeof(struct node)); 
		if(tmp -> next == NULL)
		{
			printf("Error! memory is not available\n");
			exit(0);
		}
		tmp = tmp-> next;
		tmp-> data = data;
		tmp-> next = head;
	}
	return head;
}

void printlist(struct node *head)
{
	struct node *current;
	current = head;
	if(current!= NULL)
	{
		do
		{
			printf("%d\t",current->data);
			current = current->next;
		} while (current!= head);
		printf("\n");
	}
	else
		printf("The list is empty\n");

}

void destroy(struct node *head) 
{
	struct node *current, *tmp;
	
	current = head->next;
	head->next = NULL;
	while(current != NULL) {
		tmp = current->next;
		free(current);
		current = tmp;
	}
}
void main()
{
	struct node *head = NULL;
	head = add(head,1); /* 1 */
	printlist(head);

	head = add(head,20);/* 20 */
	printlist(head);

	head = add(head,10);/* 1 20 10 */
	printlist(head);

	head = add(head,5); /* 1 20 10 5*/
	printlist(head);
	
	destroy(head);
	getchar();
}





Is This A Good Question/Topic? 0
  • +

Replies To: Linked List

#2 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1616
  • View blog
  • Posts: 5,707
  • Joined: 03-August 09

Re: Linked List

Posted 15 December 2010 - 02:48 PM

in a linked list the 'next' pointer points to the next item in the list (wait don't kill me). the next item is of the same type as the structure that contains the 'next' pointer. so each objects 'next' pointer points to an object that also has a next pointer, thus a list is formed. in you code the structure witch contains the 'next' pointer called node (witch is also very common) so the next pointer points to a dynamically allocated node.
Was This Post Helpful? 0
  • +
  • -

#3 seeP+  Icon User is offline

  • D.I.C Addict

Reputation: 55
  • View blog
  • Posts: 601
  • Joined: 20-July 09

Re: Linked List

Posted 15 December 2010 - 02:57 PM

temp->next = head;

This is connecting one node to another.
Say temp's node contains 5 and head's node contains 4 which points to 8, which points to 2. So the list of head would be 4,8,2. After the above code the list of temp would be 5,4,8,2.
Was This Post Helpful? 0
  • +
  • -

#4 isha_005  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 15-December 10

Re: Linked List

Posted 15 December 2010 - 03:03 PM

Hi
I too understand the same thing that next pointer will point to next item in the list . but this head pointer is confusing is this becoz of naming style . Can u explain me the add functn logic .
In the if section
it check if (head == NULL ) i.e if empty list then add the value to it after allocating memory
head->data = data ; i.e 1 got added.
head -> next = head ; /* what is this pointing to can u break ita nd explain*/
like head-> next->data = ??
head-> next ->next = ??
Was This Post Helpful? 0
  • +
  • -

#5 seeP+  Icon User is offline

  • D.I.C Addict

Reputation: 55
  • View blog
  • Posts: 601
  • Joined: 20-July 09

Re: Linked List

Posted 15 December 2010 - 03:08 PM

head -> next = head ; /* what is this pointing to can u break ita nd explain*/

If head is 5 the head->next will be five, thus the new head would be 5,5
Was This Post Helpful? 0
  • +
  • -

#6 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1616
  • View blog
  • Posts: 5,707
  • Joined: 03-August 09

Re: Linked List

Posted 15 December 2010 - 03:09 PM

malloc returns NULL if it cannot allocate the space for one reason or another so this is checking to make sure that the head was allocated and that there are no errors. the part where head is pointed to head implies a circularly linked list. head->next->next would be head and head->next>data would be the same as head->data. looking at the temp->next = head line i can see that this is indeed a circularly linked list.

@seeP+: no it would not be 5,5 it would just be 5. nothing was added to the list after head, that line is only run when the list is empty, e.g. it allocates the first node and links the back to the front (in that order not in reverse) and the head node would be the back and the front in this case

This post has been edited by ishkabible: 15 December 2010 - 03:14 PM

Was This Post Helpful? 0
  • +
  • -

#7 seeP+  Icon User is offline

  • D.I.C Addict

Reputation: 55
  • View blog
  • Posts: 601
  • Joined: 20-July 09

Re: Linked List

Posted 15 December 2010 - 03:18 PM

View Postishkabible, on 15 December 2010 - 02:09 PM, said:

@seeP+: no it would not be 5,5 it would just be 5. nothing was added to the list after head, that line is only run when the list is empty, e.g. it allocates the first node and links the back to the front (in that order not in reverse) and the head node would be the back and the front in this case

Um no.
#include <iostream>
using namespace std;
struct node
{
	int num;
	node *next;
	node()
	{
		next = NULL;
		num = 0;
	}
	
};//end of struct
int main()
{
    node *head = NULL;
	head = new node;
	head->num = 5;
	head->next = NULL;
	head->next = new node;
	head->next = head;
	cout<<head->num;
	cout<<head->next->num;
	cout<<"\nThe program has terminated!";cin.ignore();
	return 0;
}


Was This Post Helpful? -1
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1616
  • View blog
  • Posts: 5,707
  • Joined: 03-August 09

Re: Linked List

Posted 15 December 2010 - 03:22 PM

um yes, you made a new example that dose what you said but not what the OP is referring to. in his example head->next is not allocated but instead points to the head as a circularly linked list would. no where in the condition (when head is NULL) referred to by the OP was head->next allocated.
Was This Post Helpful? -1
  • +
  • -

#9 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2246
  • View blog
  • Posts: 9,236
  • Joined: 18-February 07

Re: Linked List

Posted 15 December 2010 - 03:27 PM

The idea of a linked list is that each node is "linked" to the next node in the list. So this can be done with pointers since the pointer can point to the next node in the list

so for example you get:

            First Node             Node 2                 Node 3 
      +-> +-----------+   +-->  +-----------+    +-->  +-----------+
      |   | Data      |   |     | Data      |    |     | Data      |
Head*-+   | Next*     | --+     | Next*     |  --+     | Next*     | --> NULL
          +-----------+         +-----------+          +-----------+


The head node is the home of the list -- USUALLY it is just the first element in the list, so the pointer head* is generally just a pointer to the first element in the list.

Each "Next*" pointer points to the "next" element in the list. If any node's "next pointer" points to head then you have a circular list - which is actually a viable structure though sometimes it represents and error.

So to keep track of a list you just need is a pointer to the first element in the list, because if you know the head node you can get to all of the nodes in the list just by following the chain down.
Was This Post Helpful? 1
  • +
  • -

#10 seeP+  Icon User is offline

  • D.I.C Addict

Reputation: 55
  • View blog
  • Posts: 601
  • Joined: 20-July 09

Re: Linked List

Posted 15 December 2010 - 03:27 PM

If it was a proper Linked List then it would have been and that is what it is based off of. He doesn't understand what it does if it was proper.
Was This Post Helpful? 0
  • +
  • -

#11 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1616
  • View blog
  • Posts: 5,707
  • Joined: 03-August 09

Re: Linked List

Posted 15 December 2010 - 04:26 PM

why are circularly linked list improper? there is a tutorial one this forum that covers them.

edit: in fact here it is. it's one of the most popular tutorials.

This post has been edited by ishkabible: 15 December 2010 - 04:29 PM

Was This Post Helpful? 0
  • +
  • -

#12 Guest_seep+*


Reputation:

Re: Linked List

Posted 15 December 2010 - 10:35 PM

When he only asked to explain
temp->next = head

I only attempted to answer that. He did not ask, "what is wrong with my code." He never builds the list he has one node each call of the function so the start is the end so I guess if you want to call the first node pointing to the first node a circular list than it is valid, but in his case it has no purpose.

Since I only was trying to answer his question about not being able to understand
temp->next = head
I only focused on that and answered that.
temp->next = head

Just looking at that, it also can mean that it is inserting(in an order) a new value at head and attaching the old head and the rest of its nodes to it.
Was This Post Helpful? 0

#13 seeP+  Icon User is offline

  • D.I.C Addict

Reputation: 55
  • View blog
  • Posts: 601
  • Joined: 20-July 09

Re: Linked List

Posted 15 December 2010 - 10:37 PM

That was weird. I was signed in and it asked me for name and it made me a guess. lol
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1