Thread: Likned lists

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    29
    Rep Power
    0

    Likned lists


    Hi
    I'm trying to create a linked list, but it doesn't seem to work.

    This is my code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct
    {
        int value;
        struct spot *next, *prev;
    } spot;
    
    void init_list(spot *tail);
    void print_list(spot *head, spot *tail);
    
    void main()
    {
       spot *head = (spot*)malloc(sizeof(spot));
       head->next=NULL;
       head->prev=NULL;
       head->value=1;
       
       spot *tail=head;
    
       init_list(tail);
       init_list(tail);
       init_list(tail);
       
       print_list(head,tail);
    }
    
    void print_list(spot *head, spot *tail)
    {
        spot *temp =head;
    
        while (temp->next != NULL)
        {
            printf("abcd\n");
            temp = temp->next;
        }
    }
    
    void init_list(spot *tail)
    {
        spot *temp = (spot*)malloc(sizeof(spot));
    
        temp->prev=tail;
        tail->next=temp;
        tail=temp;
    
        temp->value=1;
        tail->next=NULL;
    
    }
    The main idea was to create the first item and use "head" and "tail" to point at it, then use init function to create another item pointed by "temp", have temp->previous point at the current tail and tail->next point at the temp making it the new last item of the list.
    Problem is, when I try to print, it prints "abcd" only once.
    What is the problem?

    Thanks... :)
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,851
    Rep Power
    481
    You seem to want a doubly linked list and to keep track of the head and tail. Your print_list doesn't use the tail passed in as a function argument but that's not the problem. You haven't verified that malloc succeeded. But that's not the problem. main must return an int status code to the operating system. But that's not the problem. My compiler warns about incompatible types for struct spot *. But that's not the problem.

    Will the head and tail store valid data? It's wasteful if they don't. I'll rewrite in this wasteful manner anyway, because it avoids addresses of addresses. Furthermore, head and tail will be separate nodes originally because the it seems a clearer presentation. There will be no NULL pointers in the doubly linked list.

    So I suppose a problem with your code causes the symptom is that you needed to pass &tail to init_list, which would have needed a spot**tail argument, and then to update as
    *spot = new_pointer;

    Well, the implementation described in paragraph 2 is the easiest most straightforward doubly linked list code I've written.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define SPOT struct spot	/* typedef isn't in my c vocabulary */
    SPOT {
      int value;
      SPOT*next,*prev;
    };
    
    SPOT*create_spot(int value) {
      SPOT*rv = malloc(sizeof(SPOT));
      if (NULL == rv) {
        fputs("\nmemory failure\n",stderr);
        exit(1);
      }
      rv -> next = rv -> prev = NULL;
      rv -> value = value;
      return rv;
    }
    
    void print_list(SPOT*head,SPOT*tail) {
      SPOT*temp = head;
      for (temp = head->next; temp != tail; temp = temp->next)
        printf(" %d", temp->value);
      putchar('\n');
    }
    
    void push(SPOT*tail, int value) {
      /* put a new node before the tail marker */
      /* we must update 4 pointers. */
      /* Both of the new node, and those that should now point to the new node. */
      SPOT*temp = create_spot(value);
      temp->prev = tail->prev;
      temp->next = tail;
      tail->prev = temp;
      temp->prev->next = temp;
    }
    
    void enter(SPOT*head, int value) {
      /* put a node at the head of the list */
      push(head->next, value);	/* tricky! */
    }
    
    int main() {
      SPOT
        *head = create_spot(0),
        *tail = create_spot(0);
      head->next = head->prev = tail; /* connect head and tail */
      tail->next = tail->prev = head;
      push(tail, 3);
      push(tail, 4);
      enter(head, -8);
      push(tail, 5);
      enter(head, -22);
      print_list(head,tail);
      return 0;
    }
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    29
    Rep Power
    0
    Thanks, I'll give a try when I get home
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    17
    Rep Power
    0
    Here is an example using separate list structure and node structure. Only push back (append to end list) and pop front functions are shown. A single linked list is good enough if you only perform operations at the front or back of a list. A double link list is useful if you perform operations in the middle of a list. You could also add a count to the list structure to keep track of how many nodes there are in a list.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct _NODE{                       /* node struct */
        struct _NODE * next;
        struct _NODE * prev;
        int value;
    }NODE;
    
    typedef struct _LIST{                       /* list struct */
        NODE * head;
        NODE * tail;
    }LIST;
    
    void PushBack(LIST * pList, NODE * pNode)   /* append node to end list */
    {
        if(pList == NULL || pNode == NULL)
            return;
        if(pList->head == NULL)
            pList->head = pNode;
        else
            pList->tail->next = pNode;
        pNode->next = NULL;
        pNode->prev = pList->tail;
        pList->tail = pNode;
    }
    
    NODE * PopFront(LIST * pList)                /* get node from front of list */
    {
    NODE * pNode;
        if(pList == NULL || pList->head == NULL)
            return(NULL);
        pNode = pList->head;
        pList->head = pList->head->next;
        if(pList->head == NULL)
            pList->tail = NULL;
        else
            pList->head->prev = NULL;
        pNode->next = NULL;
        pNode->prev = NULL;
        return(pNode);
    }
    
    int main()                                  /* main */
    {
    LIST List = {NULL, NULL};
    NODE * pNode;
    int i;
    
        for(i = 0; i < 8; i++){                 /* test pushback */
            pNode = malloc(sizeof(*pNode));
            pNode->value = i;
            PushBack(&List, pNode);
        }
    
        for(i = 0; i < 8; i++){                 /* test popfront */
            pNode = PopFront(&List);
            printf("%d ", pNode->value);
            free(pNode);
        }
        printf("\n");
    
        return(0);
    }
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    29
    Rep Power
    0
    Thanks. :thumbs:

    One more question, if I want to search for one of the items in the list, is there a faster way other than going from the head item with a loop until the item is found?

    The problem is that if I want to compare 2 items, it seems like a horrible waste of running-time.

    I know that there are other, more efficient ways than linked list for this sort of job, but in my case I need linked lists.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    17
    Rep Power
    0
    Originally Posted by idobe
    One more question, if I want to search for one of the items in the list, is there a faster way other than going from the head item with a loop until the item is found?
    Not without some form of supplemental information, but then you'd have to maintain that supplemental information whenever elements were added to or removed from the linked list.
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    29
    Rep Power
    0
    What do you mean?
    Let's say I have a linked list of students which have names and ages(and 2 pointers next and prev), and I want to find the students named "John Doe" and "Jane Doe" and check which one is older, what can I do other than go from the first (or last) name until I find John/Jane and again until I find the other?
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    17
    Rep Power
    0
    linked lists ... faster search ... supplemental information
    Originally Posted by idobe
    What do you mean? ... linked list with names
    You could use a hash map composed of array of pointers to nodes in the linked list. You hash a name to index into the hash map. Updates to the linked list would require updates to the hash map also.
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    29
    Rep Power
    0
    So basically it's an array of pointers where each pointer points to one of the items?
    I still don't understand how is it more efficient.
    I still need to search in that array... :confused:

    Maybe I didn't understand you properly...
  18. #10
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,851
    Rep Power
    481

    Simplified


    If you chose a "middle value" in some ordering scheme, and then when building the list you put the items that are less than that middle value on the head of the linked list, and the items that are greater onto the tail, then you'd still have an O(n) search but in practice the search time will be closer to O(n/2).
    [code]Code tags[/code] are essential for python code and Makefiles!
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    17
    Rep Power
    0
    Originally Posted by rcgldr
    You could use a hash map composed of array of pointers to nodes in the linked list. You hash a name to index into the hash map. Updates to the linked list would require updates to the hash map also.
    Originally Posted by idobe
    So basically it's an array of pointers where each pointer points to one of the items?
    It's an array of pointers, but the index is a hash function with the name as input. If two names produce the same index, called a collision, then the array has to be probed again or an alternate structure is used like an array of pointers to an array of linked lists called "chaining". For good efficiency without "chaining", the number of pointers in the array should be at least 1.43 times the number of nodes in the linked list (1.43 = 1 / (.7 load factor)), and it's common to make it twice as many.

    A non-chained hash table of size k used for a linked list of size n ideally has an overhead of O(1 + n/k). For a chained hash table, it's depends on the average length of the chains.

    You could write your own mapping code, or use STL std::unordered_map template class.

    Wiki article:

    http://en.wikipedia.org/wiki/Hash_table

IMN logo majestic logo threadwatch logo seochat tools logo