Linked Lists for Dummies

This is a discussion on Linked Lists for Dummies within the C Programming forums, part of the General Programming Boards category; I'm stuck on linked lists. I'm confused as to how to create a new linked list --- there are loads ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    3

    Question Linked Lists for Dummies

    I'm stuck on linked lists. I'm confused as to how to create a new linked list --- there are loads of examples on the internet of how to iterate through a linked list that ALREADY exists, and there are examples of how to create a linked list manually with separately named nodes, or how to insert a node into a list that already exists. However, for the purposes of my homework (which involves a MUCH more complicated task than simply implementing a linked list), I'm going to need to iterate through some data, creating a linked list from it. Actually, I'm going to have to create a hash table, but BABY STEPS!

    What I would LOVE is if someone gave me a simple, dummy explanation of how to implement a linked list of 1, 2, 3.

    For my purposes, I am assuming that a struct node is

    Code:
    typedef struct node
    {
        int i;
        struct node* next;
    }
    node;
    Okay? From what I've gathered, the head node contains no value, and is declared and allocated to point to the next node as such:
    Code:
    node* head = malloc(sizeof(node));
    Soo to point it to the next node... We do something like this?

    Code:
    head->next = node* new;
    And we'd have to allocate that as well, and give it a value

    Code:
    new = malloc(sizeof(node));
    
    new->i = 1;
    [/CODE]

    Okay, good. Have I successfully made a list of 1? That's about as far as I can get. Then I want to link the node new to the next node.
    Code:
    new->next = new;
    ??????
    Here is where I get lost. Suppose that I'm actually doing this in a for loop, so I want to be able to do this 3 times. This doesn't seem right to me??

    Can someone please help and show me a simple, bare bones way to do this? Also, please let me know if I have gotten ANY of this right. I am so confused!
    I am NOT asking anyone to do my homework for me. This isn't even what my assignment is, but I can't do my assignment without grasping this concept.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,821
    Here is an example which adds nodes to the front of a list.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
        int          value;
        struct node *next;
    };
    
    struct node *prepend ( struct node *head, int value ) {
        // allocate a new node
        struct node *new = malloc( sizeof(*new) );
        
        // fill everything in
        new->value = value;
        new->next = NULL;
    
        // link to the existing linked list
        new->next = head;
        return new;
    }
    
    void print ( struct node *head ) {
        while ( head != NULL ) {
            printf("%d ", head->value );
            head = head->next;
        }
        printf("\n");
    }
    
    int main ( ) {
        struct node *head = NULL;
        int i;
        for ( i = 1 ; i <= 3 ; i++ ) {
            head = prepend(head,i);
        }
        print(head);
        return 0;
    }
    I would suggest the next thing you should try is
    struct node *append ( struct node *head, int value )
    to add a node to the end of the list, so it prints 1 2 3 when you run the code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    3

    Thank you for your help!

    I tried implementing append this way, but I get a segfault. Do you have any suggestions?
    Code:
    void append(int i)
    {    
        cursor = first;
        
        while (cursor != NULL)
        {
            cursor = cursor->next;
        }
        
        node* temp = malloc(sizeof(node));
        temp->i = i;
        temp->next = NULL;
        cursor->next = temp;
        
    }

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,821
    > cursor->next = temp;
    What is cursor always going to be, on exit from the while loop?

    You're trying to find the last node, not fall off the end.

    Also, why are cursor and first global variables all of a sudden?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Oct 2012
    Posts
    3
    Quote Originally Posted by Salem View Post
    > cursor->next = temp;
    What is cursor always going to be, on exit from the while loop?

    You're trying to find the last node, not fall off the end.

    Also, why are cursor and first global variables all of a sudden?
    You're right. I changed it to

    Code:
    void append(int i)
    {    
        cursor = first;
        
        while (cursor->next != NULL)
        {
            cursor = cursor->next;
        }
        
        node* temp = malloc(sizeof(node));
        temp->i = i;
        temp->next = NULL;
        cursor->next = temp;
        
    }
    Buuut I still get a segfault.

    They're global variables because I'm calling them in all sorts of functions (prepend, append, insert, find i, etc...)

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    That code could fail either if malloc happens to return NULL, or if first was NULL to begin with.
    It should be okay once you take care of those cases.

    Do at least try to avoid globals though.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,821
    > They're global variables because I'm calling them in all sorts of functions (prepend, append, insert, find i, etc...)
    Look at my first example - did it use global variables?
    Did it need global variables?

    > Buuut I still get a segfault.
    Because first is NULL when the program starts, and you have an empty list!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. Replies: 4
    Last Post: 05-01-2010, 11:19 PM
  3. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 02:49 AM
  4. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 12:08 PM
  5. Linked List of Linked lists Revisited.
    By Qui in forum C++ Programming
    Replies: 11
    Last Post: 04-11-2004, 10:45 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21