Linked list

[CoolAvocado]

I am newb and naive about this topic

can someone give me an example program
and teach me?

thankyou very much

[salem c]

So how much prior research have you done (aka google)?
https://en.wikipedia.org/wiki/Linked_list

[CoolAvocado]

Hmm i try but there are words that i cant understand

[CoolAvocado]

i just cant understand it by just looking and reading it

i want some to teach me from here

[CoolAvocado]

i tried also in youtube buttt if theres a part i want to ask i cant ask and get an answer

[salem c]

Youtube is filled with so much rubbish that it's not a good place to look.

Too many 3rd world kids spouting nonsense from their TurboC.

Watching people type in code badly "itn<bs><bs>nt" is one of the circles of hell.

Downloading 100MB of video bandwidth to summarise what can be written in a few K of text is awful. Plus you can't even copy/paste text from the video. And if the uploader (or your connection) decides to degrade the quality, you end up with an unreadable fuzzy mess.

Try this:
https://www.google.com/search?q=example+linked+list+in+c%2B%2B

[jonnin]

it would be best if you learn to learn from the web, but ok, why not.

the backbone of a linked list is the idea that a container can contain a pointer to its own type. That is a mouthful, so stop here and re-read that about 20 times until it sinks in. Here is an example of exactly that:

struct list
{
    list * next;
     int data;
};

that is really 90% of it.
This is sort of like looking into a pair of mirrors. a list has a pointer to a list that has inside it a pointer to a list which has inside it a pointer to a list... it can go on forever (in theory. computers have limits).

now you just "link" up a list of them. Doing that requires you to fully understand pointers, dynamic memory, and how to code using those things without making a mess. Making a list is a great exercise to drive home managing your pointers and teach you to be very careful when using them. I assume you fully understand pointers, but if you do not, and you pursue writing this, you soon will <g>.

#include <iostream>
#include <cstddef>
#define null 0  //online compiler is being stubborn
using namespace std;
struct list
{
    list * next;
     int data;
};
int main()
{
  list *x = null; // an empty list
   x = new list; //add a value to the list:
   x[0].data = 3;
  x[0].next = null; //important, the next that is null marks end of a list
  //now we have a list with a single element inside.  

  //repeat this idea: add would be a function but here I just put the code inline
  list * tmp = new list; //create a new 'node' or item in the list
  tmp[0].data = 2;  
  tmp[0].next = x;  //the new one is now linked to the original, in front of it. 
  x = tmp;          //the original is replaced by the new chain.  2->1 -> null
  tmp = new list; //one more time
  tmp[0].data = 1;
  tmp[0].next = x;   //1 -> 2 -> 3 -> null
  x = tmp;
  
  //and we now have a list with 1,2,3 inside.  
  tmp = x;  //you must not 'lose' the list itself, so you use temp pointers to navigate it.  this is critical!!!
   while(tmp) //while you are not at the null end of list pointer
    {
       cout << tmp[0].data << endl; //do something to data
      tmp = tmp[0].next;  //move to next item
    }
}

I have linked it as a stack, inserting at the top which is the most efficient way. you can insert in the middle or end, but you must manage all the pointers when you do that, and it becomes complex. You should do this once you get the basics working. You also need a delete, where you pull one out, fix the pointer chain, and delete the bad item's memory. You may want a search, to find a particular item. from there you just grow it to do what you need it to do.

Im not going to code all that, but how would you insert a value between 2 and 3?
you have to find the 2, and save a pointer to it.
then you need to have a pointer that holds two's old next, the 3 value item.
then you make a new item, as shown, outside the chain.

at this point you have 2,3 saved in temp pointers and newitem as well.

the new item should point its next to two's old next, the pointer you saved holding the 3 node.

now you have a strange Y shaped setup where 1->2->3 is a chain AND newitem->3 is a second chain. This is just an intermediate step so its ok.

Now you need to set two's next to the new one.
this completes it, the chain becomes
1->2->new->3

notes: you should probably use nullptr when you do this.
-> can be used instead of array syntax. So can *var syntax. Pointers unfortunately have many syntaxes to do the same thing.

give it a try now, if you get stuck post code and ask.
utoob has a comment section so you MAY be able to ask there. I wouldn't, but its possible. The obsession with videos is amusing to me as well, they present 5 seconds of info over 5 min. It is not a good way to teach code. Its a good way to teach how to change the oil in your car, so you can see the stuff being talked about.

[dhayden]

Here is some very simply code for a linked list.

// Linked lists for beginners
// Here is some simple code for a simple linked list of ints

// By "simple code" I mean that I have tried to avoid
// intermediate or advanced C++.

// By "simple linked list" I mean that it doesn't have
// some features of the list<> template in the standard library.
// Each node points to the next node, but not the previous one.
// Also, the list does not keep a "tail" pointer so you can
// only insert at the front of the list.

#include <iostream>

using namespace std;

// A node in the linked list contains the integer data and a pointer
// to the next item in the list.  The last item in the list MUST
// have next == nullptr
struct Node {
    int data;
    Node *next;
};

// This list itself is a separate class
class List {
public:
    List();			// construct a list
    ~List();			// delete a list
    void insert(int i);		// insert i at the front of the list
    bool remove(int i);		// remove i. Returns true on success,
				// false if i wasn't in the list
    bool contains(int i);	// returns true if i was in the list
    void clear();		// clear the list (i.e., make it empty
    bool isEmpty();		// is the list empty?
    void print(ostream &strm);	// print the list to the stream
    
private:
    Node *head;
};


List::List()			// construct a list
{
    head = nullptr;
}

List:: ~List()			// delete a list
{
    clear();
}

void List::clear()		// Delete everything in the list
{
    // You might be tempted to do something like:
    // for (Node *p = head; p; p = p->next) {
    //    delete p;
    // }
    // But that won't work.  Once you delete p, you can't rely on the
    // contents of whatever it pointed to. Specifically, you can't
    // access p->next to move to the next item.

    // So you have to remember the value of the next pointer "by hand"
    
    // Notice that I've used an unusual "for" loop here. Most
    // beginners think of "for" loops only as something that counts
    // from 1 to n or 0 to n-1. But in reality they are much more
    // flexible.  The loop below is equivalent to
    // while (head) {
    //     next = head->next;
    //     delete head;
    //     head = next;
    // }
    
    Node *next;
    for (; head; head = next) {
	next = head->next;
	delete head;
    }
}

void List::insert(int i)		// insert i at the front of
					// the list
{
    // Convince yourself that this works when the list contains some
    // items already, and when the list starts empty (head == nullptr)
    Node *p = new Node;
    p->data = i;		// set the data
    p->next = head;
    head = p;
}


bool List::remove(int i)	// remove i. Returns true on success,
				// false if i wasn't in the list
{
    Node *prev=nullptr, *cur;	// the previous and current nodes
    for (cur = head; cur; cur = cur->next) {
	if (cur->data == i) {
	    if (prev) {
		// Make the previous item skip over the current item
		prev->next = cur->next;
	    } else {
		// deleting the first item. Make head skip over it.
		head = cur->next;
	    }
	    delete cur;
	    return true;
	} else {
	    prev = cur;
	}
    }
    return false;		// didn't find it
}

bool List::contains(int i)	// returns true if i was in the list
{
    for (Node *p = head; p; p = p->next) {
	if (p->data == i) {
	    return true;
	}
    }
    return false;
}

bool List::isEmpty()		// is the list empty?
{
    return (head == nullptr);
}

void List::print(ostream &strm)	// print the list to the stream
{
    // Notice that I pass the output stream as an argument. This makes
    // the funciton much more flexible than if it always printed to
    // cout. Also notice that I don't print a newline at the end. This
    // is also to make it more flexible.
    for (Node *p = head; p; p = p->next) {
	strm << p->data;
	// If there's another item after this then print a space to
	// separate them
	if (p->next) {
	    strm << ' ';
	}
    }
}

int main()
{
    List lst;
    lst.insert(1);
    lst.insert(2);
    lst.insert(3);
    lst.insert(4);

    // Note that the list prints in the reverse order from
    // how we inserted items. That's because we always inserted at
    // the front of the list
    cout << "Initial list: ";
    lst.print(cout);
    cout << '\n';

    // Remove from middle of list
    lst.remove(3);
    cout << "After removing 3: ";
    lst.print(cout);
    cout << '\n';

    // remove from beginning
    lst.remove(4);
    cout << "After removing 4: ";
    lst.print(cout);
    cout << '\n';

    // remove from the end
    lst.remove(1);
    cout << "After removing 1: ";
    lst.print(cout);
    cout << '\n';

    lst.clear();
    cout << "After clearing: ";
    lst.print(cout);
    cout << '\n';
}

[dhayden]

Here is a shorter version that relies on a "find" function. "Find" can be hard to understand but it makes remove() and contains() almost trivial.

// Linked lists for beginners
// Here is some simple code for a simple linked list of ints

// By "simple code" I mean that I have tried to avoid
// intermediate or advanced C++.

// By "simple linked list" I mean that it doesn't have
// some features of the list<> template in the standard library.
// Each node points to the next node, but not the previous one.
// Also, the list does not keep a "tail" pointer so you can
// only insert at the front of the list.

#include <iostream>

using namespace std;

// A node in the linked list contains the integer data and a pointer
// to the next item in the list.  The last item in the list MUST
// have next == nullptr
struct Node {
    int data;
    Node *next;
};

// This list itself is a separate class
class List {
public:
    List();			// construct a list
    ~List();			// delete a list
    void insert(int i);		// insert i at the front of the list
    bool remove(int i);		// remove i. Returns true on success,
				// false if i wasn't in the list
    bool contains(int i);	// returns true if i was in the list
    void clear();		// clear the list (i.e., make it empty
    bool isEmpty();		// is the list empty?
    void print(ostream &strm);	// print the list to the stream
    
private:
    Node *head;
    Node * &find(int i);	// see description below
};


List::List()			// construct a list
{
    head = nullptr;
}

List:: ~List()			// delete a list
{
    clear();
}

void List::clear()		// Delete everything in the list
{
    // You might be tempted to do something like:
    // for (Node *p = head; p; p = p->next) {
    //    delete p;
    // }
    // But that won't work.  Once you delete p, you can't rely on the
    // contents of whatever it pointed to. Specifically, you can't
    // access p->next to move to the next item.

    // So you have to remember the value of the next pointer "by hand"
    
    // Notice that I've used an unusual "for" loop here. Most
    // beginners think of "for" loops only as something that counts
    // from 1 to n or 0 to n-1. But in reality they are much more
    // flexible.  The loop below is equivalent to
    // while (head) {
    //     next = head->next;
    //     delete head;
    //     head = next;
    // }
    
    Node *next;
    for (; head; head = next) {
	next = head->next;
	delete head;
    }
}

// If a node contains i, then there is a pointer to that node. The pointer
// is either "head", or some node's "next" pointer.  This function returns
// a reference to that pointer.  If i is NOT in the list, this returns
// a reference to the pointer that ends the list (either "head" or the
// last node's "next" pointer
Node * &List::find(int i)
{
    Node **pp, *p;
    for (pp = &head; (p = *pp); pp = &p->next) {
	if (p->data == i) {
	    break;
	}
    }
    return *pp;
}


void List::insert(int i)		// insert i at the front of
					// the list
{
    // Convince yourself that this works when the list contains some
    // items already, and when the list starts empty (head == nullptr)
    Node *p = new Node;
    p->data = i;		// set the data
    p->next = head;
    head = p;

}


bool List::remove(int i)	// remove i. Returns true on success,
				// false if i wasn't in the list
{
    Node * &ptr = find(i);
    if (ptr) {
	Node *tmp = ptr;
	ptr = ptr->next;
	delete tmp;
	return true;
    }
    return false;		// didn't find it
}

bool List::contains(int i)	// returns true if i was in the list
{
    Node * &ptr = find(i);
    return ptr != nullptr;
}

bool List::isEmpty()		// is the list empty?
{
    return (head == nullptr);
}

void List::print(ostream &strm)	// print the list to the stream
{
    // Notice that I pass the output stream as an argument. This makes
    // the funciton much more flexible than if it always printed to
    // cout. Also notice that I don't print a newline at the end. This
    // is also to make it more flexible.
    for (Node *p = head; p; p = p->next) {
	strm << p->data;
	// If there's another item after this then print a space to
	// separate them
	if (p->next) {
	    strm << ' ';
	}
    }
}

int main()
{
    List lst;
    lst.insert(1);
    lst.insert(2);
    lst.insert(3);
    lst.insert(4);

    // Note that the list prints in the reverse order from
    // how we inserted items. That's because we always inserted at
    // the front of the list
    cout << "Initial list: ";
    lst.print(cout);
    cout << '\n';

    // Remove from middle of list
    lst.remove(3);
    cout << "After removing 3: ";
    lst.print(cout);
    cout << '\n';

    // remove from beginning
    lst.remove(4);
    cout << "After removing 4: ";
    lst.print(cout);
    cout << '\n';

    // remove from the end
    lst.remove(1);
    cout << "After removing 1: ";
    lst.print(cout);
    cout << '\n';

    lst.clear();
    cout << "After clearing: ";
    lst.print(cout);
    cout << '\n';
}

[CoolAvocado]

tHANK YOUUU EVERYONEEE
FOR ANSWERING ME

[CoolAvocado]

before i start analyzing your replies

i want to make sure that i understand the meaning of pointer

so here my thought

Pointers use to copy the address of a variable? am i right?
for example

a* c;

the address of variable a is copied in c?

am i right?

[CoolAvocado]

btw i am willign to learn from you guys
thanks for the help

is it possible that i can connect on one of you?
I mean like email, messenger, or in this forum?

i mean a one on one like tutor , butt for free XD hahahaha im just a student sorry ,
I prefer messenger but i can adjust on what media you want


i want to have a mentor like you guys, people who have higher understanding i assume you master it . So yeah if someone interested I really appreciate it pls reply here tnx

and i am thankful to all of you answered me bless you all .

[Albatross]

CoolAvocado wrote:

a* c; the address of variable a is copied in c?

Nope. This declares a new variable named c that can point to a variable of type a. In other words, you do still need to assign it. I'd recommend having a read through http://www.cplusplus.com/doc/tutorial/pointers/ .

To summarize, you can get the address of a variable with the prefix & operator:

a* c = &somevar; //c starts out pointing to somevar
c = &othervar; //c now points to othervar 

As for contacting us, most of us prefer to help people in public, as that makes it more collaborative, but if you need to, you can click on our names to bring up our forum profiles, from which you should be able to send a private message.

-Albatross

EDIT: Fixed typos.

[jonnin]

you should not try to understand or code a list without going back to learn pointers first.

pointers are complex and take time to understand.
do you understand arrays?

[CoolAvocado]

i understand array quite a bit so i need to understand array and pointer first?

[dhayden]

You need to understand pointers. Did you read the tutorial that Albatross linked to?

Linked lists are all about manipulating pointers, so without a good understanding of pointers to being with, you'll be lost trying to understand linked lists.

[George P]

A tutorial on Arrays, Strings, Pointers, and References (yes, they are related):

https://www.learncpp.com/cpp-tutorial/61-arrays-part-i/

Read through the entire chapter, write some code from the examples.

[CoolAvocado]

Yes
i am reading the content of the links you said THANKYOU VERY MUCHHHH

[Satan]

salem c wrote:

Youtube is filled with so much rubbish that it's not a good place to look.

Too many 3rd world kids spouting nonsense from their TurboC.

There are some good Youtube videos as well such as videos by thenewboston and Derek Banas (and of course videos from talks like cppcon). Some people find it easier to listen than read but that's just their preference.

Not to mention that you could be less rude with "3rd world kids spouting nonsense from their TurboC". You're fortunate to have better education than they had but respect that they made those videos with the intention of helping other people.

All being said I think it's a better idea to read a book than to watch videos on Youtube, but that's just a suggestion.