Thread: Pointers Linked List

  1. #1
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    171

    Pointers Linked List

    This code is from a example in Jumping Into C++ and I understand the example. But it is a practice problem that is to write a program to remove an element from a linked list; the remove function should take just the element to be removed.

    Code:
    #include <iostream>
    
    
    using namespace std;
    
    
    struct EnemySpaceShip
    {
        int x_coordinate;
        int y_coordinate;
        int weapon_power;
        EnemySpaceShip *p_next_enemy;
    };
    
    
    EnemySpaceShip *getNewEnemy()
    {
        EnemySpaceShip *p_ship = new EnemySpaceShip;
        p_ship->x_coordinate = 0;
        p_ship->y_coordinate = 0;
        p_ship->weapon_power = 20;
        p_ship->p_next_enemy = NULL;
        return p_ship;
    }
    
    
    void updateShip(EnemySpaceShip *p_ship)
    {
        p_ship->x_coordinate += 10;
        p_ship->y_coordinate += 10;
        p_ship->weapon_power += 20;
    
    
        cout << "X: " << p_ship->x_coordinate << endl;
        cout << "Y: " << p_ship->y_coordinate << endl;
        cout << "Weapon Power: " << p_ship->weapon_power << endl;
    }
    
    
    int main()
    {
        EnemySpaceShip *getShip = getNewEnemy();
        updateShip(getShip);
        return 0;
    }
    If I got this right I will create a pointer that points to the first SHIP (getNewEnemy) and the other one will not be printed out.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    The example doesn't actually create a linked list at all. It makes a single EnemySpaceShip, then calls updateShip on that single ship. The structure does have a next pointer which is set to NULL, but that in itself doesn't make it a linked list. The updateShip() function isn't going to magically follow the list and apply to other elements in the linked list. So if you're trying to make a remove() function, maybe you should first create an insert() function?... What exactly is your question?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    171
    I have seen the code example and I know that it isn't creating a linked list. But I have no idea of how to write a program that removes a element from a linked list. Is it any website or something exaplaining linked list. Or hints that somebody can give to help me? It is one of the practice problems in Jumping Into C++ and I want to do all of them so you really can understand how pointers work

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,608
    The way to remove a singly linked list node is to point the previous node's next link to the node after the one you delete. If the remove function can only take a pointer to the node to delete, the linked list should be a doubly linked list. As a singly linked list, remove(node *removeMe) can't work: there is no way to access the previous node to the deleted node without a pointer to it.

    Making the linked list doubly linked also makes the removal more complicated. You have to set the previous nodes next link to point to the next node, and the next node's prev link to point to the previous node. In exchange though, remove(node *removeMe) does work.

    Once you reset the previous and next links, you can safely release the memory of the old node.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by whiteflags View Post
    As a singly linked list, remove(node *removeMe) can't work: there is no way to access the previous node to the deleted node without a pointer to it.
    Well, of course you can. You just have to search through the list from the beginning for the node whose next pointer equals the one to delete. Possible, but only in linear time, of course.

    For many kind of problems, it often helps to look it visually. So draw an easy picture of the node to delete, and the node before and after it. Draw lines that connects the next/prev members (the links), so you can easily see what you must do. It might also help if you draw a picture of how it's supposed to look AFTER a node is deleted.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,608
    Elysia, may I direct you to reread the OP's post.
    Quote Originally Posted by DecoratorFawn82 View Post
    the remove function should take just the element to be removed.
    An extra parameter, a pointer to the list, is not allowed, AFAICT.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    It is unclear from the context if the function that removes an element would know the head of the list. In a traditional linked list, it would. In this example, I just don't know (I don't have access to the book and this doesn't exactly look like a linked list in any traditional sense).
    If it's a traditional list, it's possible. If it doesn't have access to the head, then I am inclined to agree with you.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    A common solution is to allow deleting from a singly lined list is to use a pointer to the element prior to the one you need as the iterator, instead of a pointer to the node itself. It's ugly, but it saves on the algorithmic complexity of iterating through the list to delete an element.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem with pointers in linked list
    By django in forum C Programming
    Replies: 36
    Last Post: 07-29-2011, 10:02 AM
  2. Help a Student in C (Linked List, Pointers etc)
    By mocha1218 in forum C Programming
    Replies: 14
    Last Post: 07-02-2010, 01:38 PM
  3. Linked List with Two Pointers
    By aspekt9 in forum C Programming
    Replies: 5
    Last Post: 12-07-2009, 04:23 PM
  4. linked list and pointers : ??????
    By gemini_shooter in forum C Programming
    Replies: 7
    Last Post: 05-04-2005, 05:02 AM
  5. Linked List and Array of Pointers
    By Nish in forum C Programming
    Replies: 4
    Last Post: 03-04-2005, 04:28 PM