Hello everybody. All though I have joined recently, iv been following DANIWEB since years. I was wondering if someone could help me understand how link lists exactly work. I understand how they work in general, but when I tried to understand what the "->" operator does and how it exactly works, I got very confused. overall I do not have a very clear concept of pointers and "->" operator hence I am finding is very hard to program a linked list in which I need to insert data and print it out. If someone could just make me understand how pointers and "->" operator works, I will write some code and post it back.
UberJoker 0 Junior Poster in Training
jbennet 1,618 Most Valuable Poster Team Colleague Featured Poster
Okay, all a pointer is is a number (indeed to see it in C use the & operator). Its a number standing for a memory address (like a co-ordinate). You use -> to operate on the thing which the pointer points to.
Simply put, a linked list is a data structure which allows for dynamic memory. On the other hand, an array, for example, is one contiguous block of memory of a fixed size. This is easy to code, but not very flexible. Linked lists address this issue by allowing for variable size and (depending on implementation) faster searching, at the cost of complexity
Simply, there is a pointer (basically a numerical memory address) called head, or start etc.... This points to the first element (node) in the list (an object - linked lists are a great example of why OOP is good). If the list is empty, this points to NULL.
Each node object has some data and a field which holds a pointer (the address of the next node in the list). If this is NULL, it means it is the last node in the list.
So to traverse a list, you get each node, starting with the one at the head, and then you follow the list (by getting each nodes *next pointer) along, until you get to one where this points to NULL (the tail of the list)
LinkedLists can be used in more complex ways. E.g a Binary Search Tree. In this case, each node has a pointer to its "left" (lower value) and "right" (higher value). This is how you would store words in a dictionary, for example. This makes for quick and efficient searching as it can hold as many words as it wants, and each time you analyse a node during your search you cut the possible search pool by 50%.
UberJoker 0 Junior Poster in Training
Hey. Thanks a lot for your reply. I understood some of what you said. But I am still a little confused about how pointers and arrow operators "->" are supposed to work in a link list. Here is a little code that I was playing around. Most of it is from my book.
I understand that in a single link list you need a next pointer which has the address of the next node and in a double linklist you have previous and next. but how to set them? I am so lost here.
class LL{
private:
struct node
{
int InputData;
node *link;
}*pointer; //this pointer points to the structure called node. I think?
public:
LL();
void insertFunction(int num);
};
LL::LL()
{
pointer = NULL;//I did not get why pointer has to be NULL here.
}
void LL::insertFunction(int num)
{
node *temp,*next; //what is the point of this? So now I have a total of 3 pointers pointing to the structure node?
if(pointer == NULL)//why would pointer ever be NULL?
{
pointer = new node;
pointer -> InputData= number; //what is pointer doing here? what does -> sign do?
pointer -> link = NULL;//what is the point of this?
}
else
{
temp = pointer;//what is the point of this? Why cant i just use pointer?
while(temp -> link !=NULL)//
temp = temp->link;
next = new node;
next ->MyData = number;
next ->link = NULL;
temp ->link = next;
}
}
may be if i get this much explained, I can do the rest. If someone can explain to me what is going on here I will be grateful. This is from my book and I did not get a single thing they said.
Rashakil Fol 978 Super Senior Demiposter Team Colleague
Okay, all a pointer is is a number (indeed to see it in C use the & operator).
What the are you talking about? You don't use the & operator to see the memory address.
Its a number standing for a memory address (like a co-ordinate). You use -> to operate on the thing which the pointer points to.
Ah, yes, to "operate on something."
Simply put, a linked list is a data structure which allows for dynamic memory.
Simply put, a linked list is a tinkledoo which allows for dynamic dragonsaur.
On the other hand, an array, for example, is one contiguous block of memory of a fixed size. This is easy to code, but not very flexible. Linked lists address this issue by allowing for variable size and (depending on implementation) faster searching, at the cost of complexity
No, linked lists do not allow for faster searching; then it would be something other than a linked list.
Simply, there is a pointer (basically a numerical memory address) called head, or start etc....
Basically. Basically (basically).
This points to the first element (node) in the list (an object - linked lists are a great example of why OOP is good).
No they aren't. You don't have any clue what you're talking about. Linked lists are found in every modern language, no matter whether the paradigm is functional, object oriented, Javastyle, or ball-of-parentheses. That has nothing to do with object oriented programming.
If the list is empty, this points to NULL.
That's an implementation detail and obviously you're uncomfortable with polymorphism and thus OOP in general if you're using null pointers to denote empty lists.
LinkedLists can be used in more complex ways. E.g a Binary Search Tree.
Repeat after me: A BINARY SEARCH TREE IS NOT A LINKED LIST. NOT ALL DATA STRUCTURES THAT ARE BUILT OUT OF NODES ARE CALLED "LINKED LISTS."
A BINARY SEARCH TREE IS NOT A LINKED LIST. NOT ALL DATA STRUCTURES THAT ARE BUILT OUT OF NODES ARE CALLED "LINKED LISTS."
A BINARY SEARCH TREE IS NOT A LINKED LIST. NOT ALL DATA STRUCTURES THAT ARE BUILT OUT OF NODES ARE CALLED "LINKED LISTS."
A BINARY SEARCH TREE IS NOT A LINKED LIST. NOT ALL DATA STRUCTURES THAT ARE BUILT OUT OF NODES ARE CALLED "LINKED LISTS."
A BINARY SEARCH TREE IS NOT A LINKED LIST. NOT ALL DATA STRUCTURES THAT ARE BUILT OUT OF NODES ARE CALLED "LINKED LISTS."
A BINARY SEARCH TREE IS NOT A LINKED LIST. NOT ALL DATA STRUCTURES THAT ARE BUILT OUT OF NODES ARE CALLED "LINKED LISTS."
In this case, each node has a pointer to its "left" (lower value) and "right" (higher value).
analyse
It's "analyze." Learn how to spell and stop laboriously coloring your writing with unneighborly low-caliber letters.
UberJoker 0 Junior Poster in Training
lol...ok...can u explain me then?
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.