CODEWITHSUNDEEP
c++structlinked-list
Joshua
Joshua

Reputation: 4320

How to make a linked list in using structs?

I've seen a few topics about linked lists, and I've read enough to glean how to do it generally, but I want to make sure I'm not wrongly interpreting the information I've gathered.

Let's say I have:

struct element 
{
    int       val;
    element   *next;
};

The element *next is a pointer to an element, which will be used to connect the elements together in order to form the linked list.

I've also gathered that you need to have some kind of "tie off" so you don't lose your list. My professor describes it as a trail of balloons, and if you dont have a "tie off" your list can get lost.

So I start off with creating the "tie off" pointer:

element first;
first -> *next = 0; // or null

This is where I get lost... How do I add to the head of a linked list? Ordering it isn't important at this point, I just need to start with an unordered list, I'll get more complicated later.

Something like this?

element addMe;
addMe -> val = 100;

first -> next = *addMe;

Is that right?

What would I do to add something to a non-empty list?

Thanks for the time!

Edit: This is not homework. We have gone over linked lists, and have done an assignment with them. I did not get a very good grade on the assignment, so I am trying to strengthen my understanding before the next assignment. We will use linked lists again.

Edit2: Thanks!

I do not know if this would be considered "homework" or not. I personally do not think it is, considering I will not be using the code I posted here.

Upvotes: 1

Views: 17030

Answers (4)

Rohit Vipin Mathews
Rohit Vipin Mathews

Reputation: 11787

you got to have a first pointer or head pointer or whatever you may call it. its the pointer that is NULL when your linked list is empty. But when you add first element to the linked list add that elements node address to the hear/first pointer too. and from the 2nd node onwards append the new nodes address to end of the list (node whose next pointer is NULL) or at the star by changing head/first and then adding the current head to new head's next.

I don't know if such theory has helped. Just follow examples or write your own code. and if you encounter errors post it on SO. i guess linked list , queue, stack , etc are available on all c or c++ books.

or search for linked list in SO.

this might do for a start: Simple C++ Linked List

Upvotes: 0

Pubby
Pubby

Reputation: 53097

You generally store a pointer to the first node:

element* first = &first_node; // this "ties" it off

first->val = 5; // set first node value to 5
first->next;    // pointer to next node

If your list is empty then first should be set to NULL.

Also, the last node in your list should have next be set to NULL.

Upvotes: 0

japreiss
japreiss

Reputation: 11251

With singly-linked lists, the efficient way to add new elements is putting them at the beginning of the list. For your design, this would be:

element newHead;
newHead.next = &list;

You'll notice that newHead is now the first element, and list no longer represents the whole list. This leads to a more functional programming style, where you are creating new lists all the time (see: the cons function in Lisp).

Procedural languages like C++ generally use some wrapper structure like this:

struct list
{
    element * first;
    void prepend(element * elt)
    {
        elt->next = first;
        first = elt;
    }
}

so list prepends are expressed as changing an existing list instead of creating a new one.

With such an auxiliary structure, it is also trival to keep track of the list size, and keep a pointer to the last element for fast appends. These both come at the cost of a few extra instructions for every list operation.

Upvotes: 4

duncan
duncan

Reputation: 6293

If you want to add to the head of the list

struct element *el = (element *) malloc(sizeof(struct element));
el->val = 100;
el->next = first;

Now el is the first element, and first is the second.

In your example, you where overwriting the first element next element with a new one. You where cutting the list and inserting your new element as the second element. Everything after first is now off the list (which is also a list, but you can't access it, since you overwrote the pointer to this 3rd element).

To add to the end of the list, iterate

struct element *e;

e = first;
while (e->next !=0)
  e = e->next;

// here e is the last element. Allocate a new one and point e->next to it. And set this new one next to 0.

Upvotes: -1

Related Questions