Linked lists

This is a discussion on Linked lists within the C Programming forums, part of the General Programming Boards category; Hi there I have a question regarding linked list Lets say I have a 3 nodes list p currently points ...

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    24

    Linked lists

    Hi there

    I have a question regarding linked list

    Lets say I have a 3 nodes list

    p currently points to the first node

    I would like to remove the second node from the list

    How do I make the first node point to the last node ( i.e. delete the second one)

    Thanks for your help!
    And if you get no joy from music hall
    Remember there is always alcohol
    And If you get no joy from Gin
    Here is the abyss jump in

  2. #2
    Unregistered
    Guest
    LIST *temp, *top;


    temp = top->next; // point to second element
    top = temp->next; // point top to third element

    would this work ?

  3. #3
    Registered User
    Join Date
    May 2002
    Posts
    41
    Well, I'm a complete newbie to linked lists but just yesterday I wrote something like this. I needed a linked list where I can remove any element at any time without breaking the chain. I didn't find any example for this so I wrote it myself. It works but if somebody finds an error (something that could be done more efficient or something like that), please tell me. Here it is:

    Code:
    /* This is the structure (replace "user" with "node" or whatever you want) */
    typedef struct _user {
    	int some_data;
    	struct _user *next, *prev;
    } user;
    
    /* Global pointers to point to first and last element */
    user *first_user = NULL, *last_user = NULL;
    
    /* The function to add a new user and return a pointer to this user */
    user *add_user()
    {
    	user *new_user;
    
    	if (last_user != NULL) {
    		last_user->next = (user*) malloc (sizeof (user));
    		new_user = last_user->next;
    		new_user->next = NULL;
    		new_user->prev = last_user;
    		last_user = new_user;
    	} else {
    		new_user = (user *) malloc (sizeof (user));
    		first_user = new_user; last_user = new_user;
    		new_user->next = NULL; new_user->prev = NULL;
    	}
    
    	return new_user;
    }
    
    /* The function to delete a node and fix the chain (just use with remove_user(pointer_to_node); */
    void remove_user(user *current_user)
    {
    	user *prev_user, *next_user;
    	prev_user = current_user->prev;
    	next_user = current_user->next;
    
    	if (current_user == first_user) {
    		/* first in line so make next one the first in line if exists */
    		if (next_user != NULL) {
    			first_user = next_user;
    			next_user->prev = NULL;
    		} else {
    			first_user = NULL;
    			last_user = NULL;
    		}
    	} else {
    		/* not first in line so connect prev to next */
    		if (next_user != NULL) {
    			prev_user->next = next_user;
    			next_user->prev = prev_user;
    		} else {
    			prev_user->next = NULL;
    			last_user = prev_user;
    		}
    	}
    
    	free (current_user);
    }
    What this allows you is to add a new node at any time to the end of the list with add_user() and remove it later with remove_user().
    I use this in threads to create a node for this thread and return a pointer in myuser and later delete this node when the thread exits, like this:

    Code:
    user *myuser;
    
    myuser = add_user();
    /* do some stuff with myuser until finished */
    remove_user(myuser);
    If you would want to get and/or delete the second node in line, you could do it like this:

    Code:
    int i = 0;
    user *current_user;
    user *second_user;
    
    current_user = first_user;
    while (current_user != NULL) {
      i++;
      if (i == 2) {
        second_user = current_user;
        break;
      }
      current_user = current_user->next;
    }
    
    if (second_user != NULL)
      remove_user(second_user);
    Hope this helps.
    Last edited by Spark; 06-01-2002 at 02:26 AM.

  4. #4
    Registered User
    Join Date
    Feb 2002
    Posts
    24

    Linked Lists

    It sure will!

    I wrote p->next=p->next->next

    but yours looks better

    thanks a lot!
    And if you get no joy from music hall
    Remember there is always alcohol
    And If you get no joy from Gin
    Here is the abyss jump in

  5. #5
    Registered User
    Join Date
    Feb 2002
    Posts
    24

    Linked Lists

    thank you all!
    And if you get no joy from music hall
    Remember there is always alcohol
    And If you get no joy from Gin
    Here is the abyss jump in

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, 05: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, 09:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 07:25 PM

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