linked lists

Discussion in 'OT Technology' started by notwist, Apr 15, 2005.

  1. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    i have a pretty random question about linked lists. basically if i have a piece of data and i want to find the node that matches, how would i go about searching the link list? would I have to make separate checks at the head, tail, and middle of the list?

    also, how do i set the data members of a linked lists? like for instance:

    Code:
      char word[10]={"hello"};
      int num=5;
      
      temp = new Node;
      temp->word2 = word;
      temp->num2 = num;
      
      
    i know this wrong but how would i go about making this work?

    help OT :noes::wavey:
     
  2. hurleyint1386

    hurleyint1386 Someone has sand in their vagina

    Joined:
    Jan 6, 2005
    Messages:
    3,687
    Likes Received:
    0
    Location:
    Rochester, NY
    haha right about now i wish i paid better attention to linked lists and stacks and such. wish i could help
     
  3. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    If it's an unsorted list, then your only option is a straight linear search. Start at the head and check each node until you find a match or reach the end. If you know the list is sorted, then you can reduce the number of comparisons by doing a binary search.
     
  4. R-Type

    R-Type The Bydo Empire must die!

    Joined:
    Aug 2, 2002
    Messages:
    1,049
    Likes Received:
    0
    Location:
    CT
    the following is a very sloppy dynamically allocated linked list example I slapped together in C in a few minutes. Status: works for me™. At the bottom, you'll see how I searched for the address that contained the data I was looking for. Assuming the list is unsorted, it's simple. Step through the list until you find the address of the node where the data you are looking for is present in the element.

    Please note, I am by no means the best programmer, but, hey I tried :)...and yes I know you needed it in C++, but I would imagine the process is simliar. I'm pretty sure it offers nice macros to do alot of the dirty work you see here behind the scenes. Unfortunately, I haven't had the time to learn C++ syntax very well.

    Good luck...and yes I was bored.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct listitem {
    		int var1;
    		struct listitem *nextitem;
    	};
    
    int main(void)
    	{
    	struct listitem *liststart=NULL;
    	struct listitem *listend=NULL;
    	int i=0;
    	
    	//create initial node by allocating storage for it
    	listend=malloc(sizeof(struct listitem));
    	
    	//set end pointer to start pointer address to save startpoint
    	liststart=listend;
    	
    	//fill the list with crap allocating storage as we go
    	for (i=0;i<10;i++) {
    		listend->var1=i;
    		listend->nextitem=malloc(sizeof(struct listitem));
    		listend=listend->nextitem;
    		}
    	
    	//find the node whose var=5
    	while (liststart!=listend)
    		{
    			if(liststart->var1==5) printf("node address: 0x%p - var1: %i\n",liststart,liststart->var1);
    			liststart=liststart->nextitem;
    		}
    	}
     
  5. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    As far as storing data in a node, you've kinda got the right idea.
    But you have to be careful with pointers and storing data in buffers.
    I've extended your example to show you how you can run into trouble.

    Code:
    char word[10];
    int num = 5;
     
    strcpy(word, "hello");
     
    node *temp = new node;
     
    node->word2 = word;
    node->num2 = num;
     
    node->next = new node;
    node = node->next;
     
    strcpy(word, "world");
     
    node->word2 = word;
    node->num2 = num+1;
    
    If your intention was to store the string "hello" in the first node, and "world" in the next node, "hello" gets obliterated by "world" because you're only storing a pointer to the word buffer in each node. The end result is not what you intended since each node points to the same buffer.

    You can fix this by designing the node so that it contains it's own buffer.

    e.g.
    Code:
    struct node
    {
    char word2[10];
    int num2;
    struct node *next;
    };
    
    or, you can dynamically allocate a buffer for each node

    Code:
    struct node
    {
    char *word2;
    int num2;
    struct node *next;
    };
     
    struct node *node = new node;
    node->word2 = new char[10];
    
    then, in either case, you copy the contents of the word buffer into the node's buffer.

    Code:
    strcpy(node->word2, word);
    
    ;
     
  6. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    so what if i just want to add a number to a int variable in a class or struct?
     
  7. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    What do you mean by "add a number?"

    int my_number = 3;
    node->num2 + my_number; // ????
     
  8. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    would that work?

    like

    node->num2 = 2;
    num=1;

    node->num2 += num;
    or would it just be
    node->num2 + num; like you said?
     
  9. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Sorry about the typo, it is indeed +=
     
  10. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    thsi is what i wrote for searching the linked list

    Code:
     cin >> num;
      temp = start_ptr;
      while(temp->next != NULL){
         if (temp->num2 == num){
      	  temp->num2 +=num;
      	temp=temp->next;
      }
      
    correct me if wrong but wouldn't this check every node except the last? i'm not sure.
     
  11. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Yes, it won't look at the last node.

    replace while (temp->next != NULL) with while (temp != NULL)
     
  12. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    oh i see. :bigthumb:
     
  13. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    i have another question. how do i initialize a linked list to have a couple nodes at the beginning of the program instead of the user having to enter them all? will classes make it easier?
     
  14. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Just add the node the same way you do when you take in user input.
    You don't have to wait for user input to construct your list.
     
  15. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    so say i have a class:
    Code:
    class node
     {  
     char word[10];
     int num;
     node *next;
     }
    and i wanted to have two node objects already stored would i just do
    Code:
     temp = new node;
     temp->word = "asfasd";
     temp->num = 10;
     
    but then how would i add a second object? i would have to allocate more memory right?
     
  16. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Yes, allocate another node.

    Code:
    node *head = new node;
    strcpy(head->word, "asfasd");
    head->num = 10;
    head->next = new node;
    node *temp = head->next;
    strcpy(temp->word, "qwerty");
    temp->num = 20;
    temp->next = NULL;
    
    You can't use the assignment operator "=" with a char buffer.
    You have to copy data into the buffer.
     
  17. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0

    so is this code correct to add a third node?
    Code:
       node *head = new node;
       strcpy(head->word, "asfasd");
       head->num = 10;
       head->next = new node;
      
       node *temp = head->next;
       strcpy(temp->word, "qwerty");
       temp->num = 20;
       temp->next = new node;
      
      node *temp2 = head->next;
      strcpy(temp2->word,"uiop");
      temp2->num=30;
      temp2->next=NULL;
       
    wha header file to i need to include to use strcpy()?
     
    Last edited: Apr 16, 2005
  18. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Yes, it's correct. But do you need temp2?
    You could just do temp = temp->next;
    Don't clutter up your code with extra variables if you don't need them.
    strcpy() is in <string.h>
     
  19. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    i added string.h but its still not working. that's odd. so i have to use strcpy?
     
  20. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Well, you could do this:

    temp->word[0] = 'a';
    temp->word[1] = 's';
    temp->word[2] = 'f';
    temp->word[3] = 'a';
    temp->word[4] = 's';
    temp->word[5] = 'd';
    temp->word[6] = NULL;

    But, strcpy() exists so you don't have to.
    What compiler are you using? And, what error related to strcpy are you seeing?
     
  21. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    i'm using Dev C++.
    Code:
      In file included from d:\docume~1\carl\desktop\library.cpp:5:
      d:\docume~1\carl\desktop\library.h:14: ANSI C++ forbids declaration `strcpy' with no type
      d:\docume~1\carl\desktop\library.h:14: `int strcpy' redeclared as different kind of symbol
      D:\DEV-C_~1\Include\string.h:61: previous declaration of `char * strcpy(char *, const char *)'
      d:\docume~1\carl\desktop\library.h:14: initializer list being treated as compound expression
      d:\docume~1\carl\desktop\library.h:14: initialization to `int' from `const char *' lacks a cast
      d:\docume~1\carl\desktop\library.h:15: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:16: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:17: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:20: ANSI C++ forbids declaration `strcpy' with no type
      d:\docume~1\carl\desktop\library.h:20: redefinition of `int strcpy'
      d:\docume~1\carl\desktop\library.h:14: `int strcpy' previously defined here
      d:\docume~1\carl\desktop\library.h:20: initializer list being treated as compound expression
      d:\docume~1\carl\desktop\library.h:20: initialization to `int' from `const char *' lacks a cast
      d:\docume~1\carl\desktop\library.h:21: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:22: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:23: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:25: redefinition of `class Book * temp'
      d:\docume~1\carl\desktop\library.h:19: `class Book * temp' previously defined here
      d:\docume~1\carl\desktop\library.h:25: multiple initializations given for `temp'
      d:\docume~1\carl\desktop\library.h:26: ANSI C++ forbids declaration `strcpy' with no type
      d:\docume~1\carl\desktop\library.h:26: redefinition of `int strcpy'
      d:\docume~1\carl\desktop\library.h:20: `int strcpy' previously defined here
      d:\docume~1\carl\desktop\library.h:26: initializer list being treated as compound expression
      d:\docume~1\carl\desktop\library.h:26: initialization to `int' from `const char *' lacks a cast
      d:\docume~1\carl\desktop\library.h:27: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:28: syntax error before `->'
      d:\docume~1\carl\desktop\library.h:29: syntax error before `->'
      
      
    yeah theres alot of errors. the program was compiling fine before i added the new code.
    i'm gonna try using MS Visual Studio and see if it works there.
     
  22. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    this is the code

    Code:
     
     Book *head=new Book;
     strcpy(head->BookTitle,"Crime and Punishment");
     head->BookID = 12345;
     head->BookCopies = 3;
     head->next = new Book;
     
     Book *temp = head->next;
     strcpy(temp->BookTitle, "Ham on Rye");
     temp->BookID = 23456;
     temp->BookCopies = 2;
     temp->next = new Book;
     
     Book *temp = temp->next;
     strcpy(temp->BookTitle, "Brave New World");
     temp->BookID = 34567;
     temp->BookCopies = 4;
     temp->next=NULL;
     
     
  23. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    I bet you've got

    #include "library.h"

    before

    #include <string.h>

    It looks like you have code in library.h that uses strcpy, but you haven't included string.h yet. Put #include <string.h> before #include "library.h" and all should be well.
    And, you only need to declare Book *temp once.
     
  24. notwist

    notwist Active Member

    Joined:
    Nov 8, 2004
    Messages:
    5,738
    Likes Received:
    0
    i don't understand. what would the code look like then?
     
  25. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    Book *temp = head->next;
    .
    .
    .
    temp = temp->next;
    .
    .
    .

    The compiler is complaining because you're declaring a variable with the same name twice.
     

Share This Page