Thread: Linked lists

  1. #1
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    Linked lists

    ok I am at a total loss how to do a program with a linked lists.
    I was there in class and we went from learning malloc, calloc, realloc and free --- to --- nodes.

    I think I missed the connection here.


    The program I am to work on I suppose is a stack. Whatever that is?

    program is to have a structure linked list (???)
    and in the main, I think user is prompted if they want to PUSH or POP. PUSH being adding a node to a linked list, POP being removing/deleting a node.

    I am not sure how to start the whole thing,
    nor do I understand the purpose of a linked list, exactly.

    here's the code I have started, thus far.

    I would greatly appreciate instruction in linked lists, where to find a good explanation on any website would be A-1 good for me.

    I must be the dumbest student in the class and on this board.
    It is disheartening to not GET IT.

    Code:
    /*********************/
    /*  stack.c                 */
    /*********************/
    
    
    #include <stdio.h>
    #include (stdlib.h>
    
    
    struct node {
       int value;                      /*  1st item of node */
       struct node *next;              /*  2nd item of node */
    };
    
    struct node *first = NULL;        /*  global variable  */
    struct node *new_node;            /*  need pointers for
                                          dynamic mem alloc  */
    
    
    //are the push and pop functions voids or ints or structs????
    
    
    
    void push()    //what the heck is this code doing???
    {
    new_node=malloc(sizeof(struct node));
    new_node->value = 17;      
    new_node->next = first;
    first = new_node;
    }
    
    
    void pop()
    {
          // do I type the same type of code here as in the push function
    }
    
    
    
    main()
    {
       int user_value;
    
       for( ; ; )   {
         printf("Enter new item\n");
         scanf("%d",&user_value);
       
       // have no idea where to go from here in for-loop
       }
    
    // instructor said something about inserting a switch
        I don't know what the cases would be in a switch statement
    
    
    
    
    }
    Sue B.

    dazed and confused


  2. #2
    Unregistered
    Guest
    A stack is exactly that. Think of it this:
    1) take a piece of paper.
    ... a) write a number on it
    ... b) set it on the table
    2) goto 1

    There is a stack. You cannot get the first item you put in the stack until you remove all the stuff on top of it.

    A "Push" function is the act of your writing a number on a piece of paper and sticking it on top of the pile.

    A "Pop" function is the act of you taking a sheet of paper off of the top, and reading the number from it.

    A linked list, in this case, represents the entire stack. A "Node" is a sheet of paper, containing the reference to the next item int the list, and the value written on the paper.

    A linked list must have an "anchor point" to hold the list, so you can keep track of where it's at in memory. Think of this as the table to which you're adding your paper. (Not the best example but it'll do.)

    Ok, so what you do, is define what a node consists of:
    Code:
    /**
    *** Define the node.
    **/
    struct node {
       struct node *next; /** the next item in the list **/
       int data; /** the data on this piece of paper **/
    };
    Define an anchor point:

    struct node *myList;

    Make sure and set this to "NULL".

    myList = NULL;

    Define a push function. Now, your push function has to have
    something to push, so we make it take a value as an argument.

    void Push( int value )
    {
    struct node *newNode;

    /**
    *** Create a new node so we can put data into it.
    **/
    newNode = malloc( sizeof( struct node ) );

    /**
    *** Put a value into this node we've just created.
    **/
    node->data = value;

    /**
    *** If the list is not empty...
    **/
    if( myList != NULL )
    {
    /**
    *** Set this node to point to the top of the list.
    **/
    newNode->next = myList;
    }
    else
    {
    /**
    *** Set the 'next' to nothing...
    **/
    newNode->next = NULL;
    }
    /**
    *** Now, stick this to the top of the stack.
    **/
    myList = newNode;
    }
    [/code]

    Pop works just the opposite:
    1) take the value out of the node
    2) pull the top node off the stack
    3) free up that node we just pulled

    Quzah.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    *mutter* damn timer

    Quzah.

  4. #4
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    Thanks, Quzah. I think I have a better idea of linked lists.
    Your imagery helped a lot.

    Let me get to writing more code. I'll see what I come up with.
    Sue B.

    dazed and confused


  5. #5
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Also, if you use the search option on this website, you should find lots of examples of stacks. Use the search word 'stack'.

  6. #6
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    POP function not working

    Why is the Pop Function not working?
    Giving me a SegFault error

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
       int value;
       struct node *next;
    };
    
    struct node *first = NULL;
    struct node *new_node;
    void push( int input_value);
    void pop(int removed_value);    here's prototype
    void instructions(void);
    void printlist();
    
    main()
    {
       int input, value, number;
    
       instructions();
       printf("?");
       scanf("%d", &input);
    
       while (input != 0)  {
          switch (input)  {
             case 1:
                printf("Enter an integer: ");
                scanf("\n%d", &number);
                push(number);
                printlist();
                break;
             case 2:
                pop(number);     here's call of function
                printf("%d removed\n", number);
                printlist();
                break;
             default:
                printf("Invalid choice.\n\n");
                break;
          }
          printf("?");
          scanf("%d", &input);
       }
       printf("End of run.\n");
       return 0;
    }
    
    void push( int input_value)
    {
       new_node = malloc(sizeof(struct node));
       new_node->value = input_value;
       new_node->next = first;
       first = new_node;
    }
    
    void pop(int removed_value)     here's function itself
    {
       if (removed_value == new_node-> value)  {
         first = new_node->next;
         free(new_node);
       }
    
       else
         printf("list is empty");
    }
    
    void instructions (void)
    {
       printf("Enter your choice:\n"
              "  0 to end program.\n"
              "  1 to add a value to the list.\n"
              "  2 to remove a value from the list.\n");
    }
    
    void printlist()
    {
       if (new_node == NULL)
           printf("List is empty.\n\n");
       else  {
           printf("The list is:\n");
    
         while (new_node != NULL)  {
    
            printf("%d --> ", new_node->value);
            new_node = new_node->next;
    
         }
    
         printf("NULL\n\n");
       }
    }
    Sue B.

    dazed and confused


  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    A pop function should take no arguments. It only pops off the top item in the list:
    Code:
    int pop( void )
    {
       struct node *n;
       int returnValue;
    
       if( myList == NULL )
          return -1; /* Or whatever you use for error. */
    
       
       n = myList;
       myList = myList->next;
       returnValue = n->value;
       free( n );
       return returnValue;
    }
    Quzah.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  2. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  3. Linked Lists Integer addition ? HELP Please??
    By green_eel in forum C Programming
    Replies: 3
    Last Post: 03-12-2003, 04:36 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM