Thread: double linked list

  1. #1
    Registered User TNA$H's Avatar
    Join Date
    Jun 2008
    Location
    Harare, Zimbabwe
    Posts
    8

    Talking double linked list

    I was given an assignment to write and implement a program to create a double linked list, delete, insert, find, display and reverse the contents of the double linked list.
    Can any one give me ideas especially on what to put on the menu. I intend to use dynamic allocation in the functions

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Doubly Linked List
    To get you started. What kind of help are you looking for?
    Start by creating a struct with the components that you will need for an element of a doubly linked list. Then post what you have and we can discuss it.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Your menu, probably, should have the same things that you've been assigned to do:
    - insert (add)
    - delete (remove)
    - search (find)
    - display (list)
    - reverse

    Now, that's the easy stuff.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Mar 2008
    Location
    India
    Posts
    133

    Smile

    I think insert and delete can be futher extended .


    1) insert right
    2) insert left

    3) delete right
    4) delete right

    a simple 3 node linked list may appear like this
    ______ _______ ________
    [_|__|_] --->[_|___|_] --->[_|____|_]

  5. #5
    Registered User TNA$H's Avatar
    Join Date
    Jun 2008
    Location
    Harare, Zimbabwe
    Posts
    8

    Question Linked lists (CT108)

    Okay I get that part, now the problem here is with the reverse function. If you were me would you implement the display function that shows the list in reverse or rearrange the whole list in reverse order.

    In the program I was thinking of sorting the list into e.g. alphabetical order, is that possible? I will post the code tommorrow, today I just wanted some ideas to add to my own to start with.
    Before I start, in the find function, is it possible to search for a node by its contents or its always by its possition

  6. #6
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    I'm guessing that reverse the list, means to actually reverse the list, which is trivial with a doubly linked list.
    You can of course search for an item by contents as well as position, but note that neither one has an advantage over the other in terms of how quickly you get to that item.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by TNA$H View Post
    Okay I get that part, now the problem here is with the reverse function. If you were me would you implement the display function that shows the list in reverse or rearrange the whole list in reverse order.
    Either will show the list in reverse order, but it really depends on the specifications if you should reverse the list itself, or just display the list in reverse order. The way you wrote the original post implies that the list itself should be reversed, but that may be just the way you wrote it, rather than the wording of the original assignment specifications.
    In the program I was thinking of sorting the list into e.g. alphabetical order, is that possible? I will post the code tommorrow, today I just wanted some ideas to add to my own to start with.
    Before I start, in the find function, is it possible to search for a node by its contents or its always by its possition
    In general, linked lists (single and double) do not have any concept of position [aside from first and last nodes are usually "special"]. Of course, there are ways to implement a linked list variant in an array, but that doesn't seem like the solution you are looking for/at.

    Sorting existing linked lists is a pain. It is much easier using insertion sort - so you either rebuild a second, sorted, list, or you insert the items in the list sorted. However, unless your tutor or such has specifically asked for this, I would leave it out until you have the remaining part of the code working.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User TNA$H's Avatar
    Join Date
    Jun 2008
    Location
    Harare, Zimbabwe
    Posts
    8
    Thanx for the site, hope its going to be very useful. Do you have any sites where i can get good code for use at school?

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by TNA$H View Post
    Thanx for the site, hope its going to be very useful. Do you have any sites where i can get good code for use at school?
    The purpose of writing your own code is to learn from the experience. To copy-and-paste the code from somewhere is like trying to learn to drive by watching racing driving on TV.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User TNA$H's Avatar
    Join Date
    Jun 2008
    Location
    Harare, Zimbabwe
    Posts
    8
    Thanx for the advice, gotta go for now. Will post the code tmrw, hopefully the ideas you gave me and those that i have are going to work

  11. #11
    Registered User
    Join Date
    Jun 2008
    Posts
    1

    ct108 assghn

    understand singly linked lists first,then you may be fine.also know your pointers well.

  12. #12
    Registered User TNA$H's Avatar
    Join Date
    Jun 2008
    Location
    Harare, Zimbabwe
    Posts
    8
    Start by creating a struct with the components that you will need for an element of a doubly linked list. Then post what you have and we can discuss it.
    So far this is what I've been able to do.
    Where I've quoted the code, I'm still working on that part.
    I really need help on
    case 1:{ //create();

    and case 2://find();
    How do I define the functions. I'm very confused on which values to pass into the functions and how to pass them.
    #include "stdio.h"


    void main()
    {
    int option,pstn;
    struct details {
    char name[25];
    struct details *prev, *next;
    } *start, *point, *prior;
    clrscr();
    start=point=prior=NULL;
    do
    {
    printf("\n\n\t MAIN MENU\n");
    printf("\n1\t Create a list");
    printf("\n2\t Insert");
    printf("\n3\t Delete");
    printf("\n4\t Find");
    printf("\n5\t Sort");
    printf("\n6\t Display list");
    printf("\n7\t Exit program\n\n Enter your choice\t");

    scanf("%d",&option);

    switch (option)
    {
    case 1: { //create();
    char c;
    start=(struct details *)malloc(sizeof(struct details));
    printf("\n Name:\t\t");
    scanf("%s",start->name);
    prior=start;
    start->prev=start->next=NULL;
    printf("\n\n Press q to go back to the MAIN NENU");
    if((c=getch())=='q')
    break;
    else
    {
    do
    {
    point = (struct details *)malloc(sizeof(struct details));
    printf("\n Name\t\t\t");
    scanf("%s",point->name);
    prior->next = point; /* point last "next" to this record */
    point->prev = prior; /* point this record's prev to prior*/
    point->next = NULL; /* point this "next" to NULL */
    prior = point; /* this is now the prior record */
    printf("\n\n Press q to go back to the MAIN NENU");
    c=getch();
    } while( c != 'q' );
    }
    break;
    }
    /*case 2: { //insert(); break;
    clrscr();
    printf("\n\n Insert record after which position");
    printf("\n\t Enter position: ");
    scanf("%d",&pstn);





    } */
    //case 3: { delete(); break; }
    case 4: { //find(); break;
    int a,n;
    clrscr();
    if(start==NULL)
    {
    printf(" List is Empty ");
    getch();
    break;
    }
    printf("\n\n Find:- \n [1] Name \n [2] Node ? ");
    scanf("%d",&option);
    if(option==1)
    { char strng[25];


    printf("\nEnter name of student that you wish to search for\n\t");
    scanf("%s",strng);
    point=start;
    n=1;
    while(point->next != NULL)
    {
    n++;
    if(strcmp(strng,point->name)==0)
    printf("[%s] found in node %d\n",point->name,n);
    else if(point == NULL && strcmp(strng,point->name)!=0)
    printf("No match found for \"%s\"",strng);
    point=point->next;
    }


    getch();

    }

    if(option == 2)
    { point=start;

    printf("\n Enter position of node");
    scanf("%d",a);
    if(a>=1)
    {
    {
    for(n=1;n<=a;n++)
    point=point->next;
    }
    //else should return NULL
    printf("Node %d is \"%s\"",a,point->name);
    }
    else {
    printf("Invalid input");
    getch();
    break;
    }
    }

    }
    //case 5: { sort(); break; }
    //case 6: { display(); break; }
    //case 7: break;
    }
    } while( option != 7);
    printf(" The end!!!");
    getch();
    }

  13. #13
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    First and foremost, you need to indent your code properly! There's no way anyone can read that.

    You'll also need to define the struct for the list outside of your main() function, so that it is accessible to all parts of your program.

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  14. #14
    Registered User TNA$H's Avatar
    Join Date
    Jun 2008
    Location
    Harare, Zimbabwe
    Posts
    8
    Sorry about that
    Code:
     
    #include "stdio.h" void main() { int option,pstn; struct details { char name[25]; struct details *prev, *next; }; struct details *start, *point, *prior; clrscr(); start=point=prior=NULL; do { printf("\n\n\t MAIN MENU\n"); printf("\n1\t Create a list"); printf("\n2\t Insert"); printf("\n3\t Delete"); printf("\n4\t Find"); printf("\n5\t Sort"); printf("\n6\t Display list"); printf("\n7\t Exit program\n\n Enter your choice\t"); scanf("%d",&option); switch (option) { case 1: { //create(); char c; start=(struct details *)malloc(sizeof(struct details)); printf("\n Name:\t\t"); scanf("%s",start->name); prior=start; start->prev=start->next=NULL; printf("\n\n Press q to go back to the MAIN NENU"); if((c=getch())=='q') break; else { do { point = (struct details *)malloc(sizeof(struct details)); printf("\n Name\t\t\t"); scanf("%s",point->name); prior->next = point; /* point last "next" to this record */ point->prev = prior; /* point this record's prev to prior*/ point->next = NULL; /* point this "next" to NULL */ prior = point; /* this is now the prior record */ printf("\n\n Press q to go back to the MAIN NENU"); c=getch(); } while( c != 'q' ); } break; } case 4: { //find(); int a,n; clrscr(); if(start==NULL) { printf(" List is Empty "); getch(); break; } printf("\n\n Find:- \n [1] Name \n [2] Node ? "); scanf("%d",&option); if(option==1) { char strng[25]; printf("\nEnter name of student that you wish to search for\n\t"); scanf("%s",strng); point=start; n=1; while(point->next != NULL) { n++; if(strcmp(strng,point->name)==0) printf("[%s] found in node %d\n",point->name,n); else if(point == NULL && strcmp(strng,point->name)!=0) printf("No match found for \"%s\"",strng); point=point->next; } getch(); } else if(option == 2) { point=start; printf("\n Enter position of node"); scanf("%d",a); if(a>=1) { for(n=1;n<=a;n++) point=point->next; } //else should return NULL printf("Node %d is \"%s\"",a,point->name); } else { printf("Invalid input"); getch(); break; } } } } while( option != 7); printf(" The end!!!"); getch(); }
    Isnt the structure going to be accessible to the other functions by use of pointers?

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by TNA$H View Post
    Isnt the structure going to be accessible to the other functions by use of pointers?
    Well, yes, but a pointer to what? You can pass it as a void *, but you won't be able to access any of the members of the structures, which makes the whole thing seem extra pointless. For the function to be able to deal with a struct details, it must know what a struct details is, and for that to happen it must be able to "see" the definition of the struct (i.e., it can't be hidden inside a different function).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked List Problem
    By Shiggins in forum C++ Programming
    Replies: 4
    Last Post: 03-10-2009, 07:15 AM
  2. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM