Can someone explain Linked List to me?

No I'm not asking about how to write one, I want to know about the data that the linked list stores. If I had a list with the following:

Code:

template<typename T>
class List {
private:
  struct Node {
    Node* prev;
    Node* next;
    T data;
  };
  
  Node* head;
  Node* tail;
  unsigned size;
...

Would this function destory the list?

Code:

  void destoryList(void) {
    Node* dest_h = head;
    Node* dest_t = tail;
    while(dest_h != 0) {
      showData(&(dest_h->data), &(dest_t->data)); // This is a test func, ignore please
      head = head->next;
      tail = tail->prev;
      delete dest_h;
      delete dest_t;
      dest_h = head;
      dest_t = tail;
    }
    return;
  }

If I had created the node by using the next pointer for every new node, everytime I attempt to delete a node I have to do delete on both it's prev and next pointers, I thought that delete would destory the entire Node. How does this work?

And what about the data? Once I use the function to delete all the prev and next pointers in the list, how would be data be deleted? Are the data on the stack? Even though the node is created dynamically?

Thanks for any help.

Would this function destory the list?

1)What happens when you are deleting and there are say 3 elements in the list and you get to the middle?

2)What happens when the head moves to the right of the middle and the tail moves to the left of the middle?

Try this code:

Code:

int* n = new int;
delete n;
cout<<n<<endl;

Does n equal 0?

I thought that delete would destory the entire Node. How does this work?

delete releases the memory set aside for a Node object. If a Node object has a member that is a pointer variable, then deleting the Node object releases the memory set aside to store an address. If there is something stored at that address that was created with new, then you need to delete that something before deleting the Node--otherwise you will lose your reference to that something.

Problem is, if I follow prelude's way of destorying a list, that means deleting every next pointer. Then if I happen to start at tail and going through the prev pointers I can still access the data. The next pointers are all gone, but the prev pointers can still be used even though they were not used to create a new node.

To answer...
1) The function would just delete the same pointer twice, not much of a problem I think, I've checked this with the addresses function, they will be the same. So delete is performed on a null pointer.

2) Nothing, I've stated above about the problem with prev and next pointers, that's why I had to delete them both, I have verified the addresses, yes when they cross over the prev pointer would point to the address of the 1st deleted next pointer in a three item list and vice verse for the next pointer. So delete again is done on a null pointer. I've done this to get rid of the problem mentioned above.

I can't dereference "n" but it's still pointing to an address.

I worrying about the data eating up memory, after I delete every possible pointer with that function, how is the "T data" released? I am certain that they are on the stack but a bit unsure, can you clarify this?

1) The function would just delete the same pointer twice, not much of a problem I think, I've checked this with the addresses function, they will be the same. So delete is performed on a null pointer.

What in your estimation is a "null pointer"?

how is the "T data" released?

deleting a Node releases all the memory used by the Node.

Then if I happen to start at tail and going through the prev pointers I can still access the data.

Really? Please provide a small test program demonstrating two pointers pointing to something that was created with new, and after deleting that something you can still access it with one of the pointers.

The next pointers are all gone

No they are not. The pointers do not go anywhere. The pointer variables still exist, and you can use them to store other addresses if you like. However, the memory they point to is released back to the system, and your program does not own it anymore.

It's hard to believe isn't it...

Code:

#include <iostream>

template<typename T>
struct ListNode {
  ListNode* prev;
  ListNode* next;
  T data;
};

typedef ListNode<int> Node;

int main() {
  Node* head = new Node;
  head->prev = 0;
  head->next = 0;
  head->data = 1;
  
  Node* tail = head;
  tail->next = new Node;
  tail = tail->next;
  tail->prev = head;
  tail->next = 0;
  tail->data = 2;
  
  Node* kill = head;
  while(kill != 0) {
    head = head->next;
    delete kill;
    kill = head;
  }
  delete head;
  delete tail;
  
  Node* some = tail;
  std::cout << some->data;
  some = some->prev;
  std::cout << " ";
  std::cout << some->data;
  
  std::cin.get();
  return 0;
}

The result I've got is "2 1", I did not set head and tail to null because I wanted to test it. Offcourse setting them to 0 will cause an error but I wanted to see if the data is deleted. If it is, it should cause an runtime error.

Edit: My posts are really bad everytime I'm in a bad situation, I'm trying to work on this and solving 8^x*4^(x+1) = 48... anyway I'm not really stupid just sometimes confused.

I know what is a null pointer, ptr = 0x0, and how delete works, just confused sometimes and write down things without thinking.

Not sure what post of Prelude's you got your example but http://faq.cprogramming.com/cgi-bin/...&id=1073086407 has a spot where she explains deleting an entire list. Basicly she creates a temporary pointer to the next node, deletes the current node, and uses the temporary next pointer to repeat the process until nothing is left.

Yes, well I'm not an idiot, read the code, it does exactly that. The only difference is that in the example, the pointer to the beginning of the list is used for delete, in my own I used another pointer to do the job instead and moves the list pointer down as I delete the nodes. But if you so insist for me to use Prelude's solution fine, the result is still the same.

Code:

#include <iostream>

template<typename T>
struct ListNode {
  ListNode* prev;
  ListNode* next;
  T data;
};

typedef ListNode<int> Node;

int main() {
  Node* head = new Node;
  head->prev = 0;
  head->next = 0;
  head->data = 1;
  
  Node* tail = head;
  tail->next = new Node;
  tail = tail->next;
  tail->prev = head;
  tail->next = 0;
  tail->data = 2;
  
  Node* save = head; // Here, just like the example
  while(head != 0) {
    save = save->next;
    delete head;
    head = save;
  }
  delete head; // extra reassurance, even removed the result is still the same
  delete tail;
  
  Node* some = tail;
  std::cout << some->data << " " << &(some->data);
  some = some->prev;
  std::cout << " ";
  std::cout << some->data << " " << &(some->data);
  
  std::cin.get();
  return 0;
}

I can still access the data through the prev pointers. I see why some software only uses singly linked lists now.

I'm still just a beginner, so i didn't see the relation between your original code and hers.
So the problem is that delete head (in the post just above) is only releasing the pointer when it should release the entire node?

Code:

#include <iostream>

template<typename T>
struct ListNode
{
	ListNode* prev;
	ListNode* next;
	T data;
};

typedef ListNode<int> Node;

int main() 
{
	Node* head = new Node;
	head->prev = NULL;
	head->next = NULL;
	head->data = 1;

	Node* tail = head;
	tail->next = new Node;
	tail = tail->next;
	tail->prev = head;
	tail->next = NULL;
	tail->data = 2;
	
	Node* save = head; // Here, just like the example
	while(head != NULL) {
		save = save->next;
		delete head;
		head = save;
	}
	delete head; // extra reassurance, even removed the result is still the same
//	delete tail;  I get Debug Assertion Failed at runtime if not commented
	Node* some = tail;
	std::cout << some->data << " " << &(some->data);
	some = some->prev;
	std::cout << " ";
	std::cout << some->data << " " << &(some->data); //exception here

	std::cin.get();
	return 0;

Unhandled exception at 0x0041160e in testlinklist.exe: 0xC0000005: Access violation reading location 0x0000008e.
Output at that time is -17891602 00355BD8
Does this mean it works fine for me? I'm using VC++ 2005 express

Yes, it should generate an error like for your compiler. It could be that delete is incorrectly implemented for mine. Did you get an exception for the first save->data? I'm using Dev-C++.

It's kind of weird how you couldn't delete an pointer again, have you tried removing both the delete head and tail? When I did, the result is still the same, only if I could output the binary into a textfile to check what went wrong.

I did recompiler and rebuild-all, no avail, I can still access the data. Could be just the compiler's fault. If I do debug now I may get the blue screen so I'll just post this and if successful I'll make an reply after the next poster.

Edit: Attempt to debug, exception occured. A friend told me that on some systems, when memory is cleared the data remains, such as Linux or Solaris when using virtual memory, he said it could be that allows me to access the data, but when I checked the location of the pointers and the data, they are 8 bytes apart. The pointers are not assigned to point to the data though so how could it access it?

Really? Please provide a small test program demonstrating two pointers pointing to something that was created with new, and after deleting that something you can still access it with one of the pointers.

Since you seem unable to provide such an example, here is an example which demonstrates a different result using dev c++:

Code:

#include <iostream>
using namespace std;
      
int main()
{
    int* p = new int;
    *p = 10;
    
    int* q = p;
    
    delete p;
    cout<<*q<<endl;  //0.  According to you, this should be 10.
    cout<<*p<<endl;  //0.  According to you, this should be 10.
            
    system("PAUSE");
    return 0;
}

Memory address overbound, it is using virtual memory, I guess that's why the data are so "persistent", problem solved.

"Persistent"? You know, the computer doesn't destroy the RAM just because you release memory. Allocating memory doesn't mean creating it.

In the simplest of systems, all that happens when you allocate a block of memory is that the heap management is told that this block of memory is now allocated, so that it doesn't hand it out to anyone else. (In more complicated systems, the OS might have to map memory to the address range first, but that's transparent and irrelevant to the application.) Similarly, when you release the memory, all that happens is that the management is told that the block is free again. But the memory is still there, and until somebody else allocates the same block, it will be unmodified as well. (Unless you have a debugging delete, which might zero out the memory.) That's why you can still travel the nodes. That's why they call C and C++ unsafe languages.
Bottom line: you don't access pointers you know to be invalid. The language permits it, but you just don't. And you especially don't complain about whatever happens when you do.

No, what I mean is, since I'm using the hard disk as virtual memory, after the data has been writing to it, I'm surprised that the OS didn't erase it after the process has ended. The data is on the harddisk somewhere, same as the test I've done on the list 3 weeks ago.

Possible. It depends on the amount of RAM you have, of course.
Why should the OS erase anything? It's just a waste of time.