Linked Lists

**bigblack** · 02-04-2002

i've read up on linked lists both online and through a textbook, but i'm still a bit in the dark. i understand that pointers point to the address of memory & can also be used to output the data that is in a certain area of memory. my problem is understanding exactly what the memory locations are and how i can link to nodes of information.

Example:
The user enters a string and wants to delete a letter from that string. i could make that work just using an if statement to not allow the letter to be printed out, but i need to use linked lists for this.

Any help would be appreciated, even if you don't think it would be useful

**golfinguy4** · 02-04-2002

1) Have each node contain a character.
2) To eliminate a char, set the previous node's next value equal to the next one's next( next=next->next)
3) Make sure you delete the node you are eliminating if you are putting it on the free store (heap)

**genghis** · 02-04-2002

Sorry if this might sound a bit redundant for you, but I dont know what you know.

Understanding pointers isn't really about how they work, it's more about their practicality. One of the advantages about pointers is that they can point to an dynamically allocated memory. If you think about it, other than pointers, there is no simple, good way to refer to memory that you simply don't know the size of or whose size is constantly changing.

The first purpose of linked lists is to harness the power of dynamically sizing memory by encapsulating it into an easy to use array-like class.

Here is how a linked list works:

There a pointer called a head pointer. It points to the first object in a list. Each object is called a node. The node contains two parts: the data section and and additional pointer variable specifying the location of the next node. In order to specify the end of the list, we need to use some sort of marker. To keep this marker simple, we'll set the 'next node location' pointer to zero when there is no other node in the list. If your worried that a memory location for the next node could be zero, don't be. That space in your program is always reserved for the operating system to maintain your program. The only other thing to keep note of with linked lists is to tell the system to deallocate the memory after your done using it. This is accomplished via the 'delete' call.

Now for the example (linked lists aren't good for strings tho):
Let's suppose the user entered in: "Hello"

the linked list looks as follows:
head -> H -> e -> l -> l -> o -> (zero)

Now we want to take out the 'e'. We start from the head and take a look at the node it points to. The data section contains an 'H'. Therefore we check the 'next node' pointer and continue down the list. The next node's data section includes an 'e', so we need to cut it out. In order to cut this letter out, we need to get the following arragment:

head -> H -> l -> l -> o -> (zero)

This involves deleting the node containing 'e' through the use of the 'next node' pointer from the first node containing the 'H'. Before we do this though, we must save the location of where the next node after the 'e' is. Once we are done deleting the 'e' node we simply set the 'H' node's 'next node' pointer to point to the one 'e' was pointing to (i.e. 'l').

Well, I hope I made sense.

**bigblack** · 02-04-2002

i understand the logic behind what you're saying but the coding is where my problem lies. i need to use structures for this project. i've read up on structures too, but it didn't seem to be enough.
could you elaborate for me please?
i still don't understand the very concept of the memory addresses.

**zMan** · 02-05-2002

This should give you some clue of how and insertion at tail works... Notice that although I added a pointer for the tail
you only need to know the head. However knowing the tail helps.
Some of the operations that a linked list should perform are

Insertion ... cases at head, in middle, at tail
Deletions ... case from head, middle, at tail
Search .. where the search returns the node pointer if found or null otherwise

Usually you use your search function to get a pointer for the node you are goind to delete.. usually you will need the pointer to the previous node or the one before in the chain...

head---->node1-->node2-->target-->node4-->tail

//** ofcourse you must also consider if the node you are deleting
//** is the head or the tail... this FindNode function
//** would return NULL if it was the head....

LNode* prevnode = FindNode(....by value...);

if( prevnode != NULL)
{
LNode* temp;

//hold temp pointer to target
temp = prevnode ->pNext;

//connect to node4
prevnode ->pNext = temp->pNext;

//disconnect target
delete temp;
}

[/CODE]

struct LNode{

char data;
char* pNext;
};

LNode* pHead = NULL;
LNode* pTail = NULL;

void AddToTail( char Data)
{

//** Special case where head is NULL
if( pHead == NULL )
{
pHead = new LNode;

pHead->pNext = NULL;
pHead->Data = Data;
pTail = pHead; //head and tail are the same
}
else
{
LNode* temp;
temp = new LNode; //create a new node from the heap

temp->pNext = NULL; //set its next member to null
temp->Data = Data; //set its data member
pTail->pNext = temp; //attach it to the tail
pTail = temp; //new node is now also the tail
}
}

[/CODE]

**zMan** · 02-05-2002

oops! Sorry!

Code:

head---->node1-->node2-->target-->node4-->tail 

//** ofcourse you must also consider if the node you are deleting 
//** is the head or the tail... this FindNode function 
//** would return NULL if it was the head.... 


LNode* prevnode = FindNode(....by value...); 

if( prevnode != NULL) 
{ 
        LNode* temp; 

       //hold temp pointer to target 
       temp = prevnode ->pNext; 

       //connect to node4 
      prevnode ->pNext = temp->pNext; 


       //disconnect target 
       delete temp; 
} 





struct LNode{ 
  char data; 
  char* pNext; 
}; 


LNode* pHead = NULL; 
LNode* pTail = NULL; 

void AddToTail( char Data) 
{ 

     //** Special case where head is NULL 
     if( pHead == NULL ) 
    { 
             pHead = new LNode; 

            pHead->pNext = NULL; 
            pHead->Data = Data; 
            pTail = pHead; //head and tail are the same 
    } 
    else 
   { 
            LNode* temp; 
            temp = new LNode; //create a new node from the heap 

            temp->pNext = NULL; //set its next member to null 
            temp->Data = Data; //set its data member 
            pTail->pNext = temp; //attach it to the tail 
            pTail = temp; //new node is now also the tail 
      } 
}

__________________
zMan

**incognito** · 02-05-2002

I am having problems with linked lists right now, I am still trying to learn them, but I guess I should learn them some day, they seem to be hard, and Jesse Liberty does not do a good job of explaining them on his 21 days book. Although I think that the book is quite good. In fact I am about to start reading some more on linked lists. I have a really good link to a linked list tutorial that teaches you how to change and store the age of something in a link list, so it gives you some ideas of what you can use it for, if you want I could give you a link to it, PM me or something.

Unregistered · 02-05-2002

here's an analogy that might help you visualize memory and how it relates to pointers. First think of the numbers in a phone book. Each telephone number is the same length, 7 digits with a hyphen between the third and fourth digit. Each number corresponds to some entity. We don't need to know where the entity is to contact them, we just need to know their number. The entity could be a residence, a business, a hospital, an empty warehouse, whatever. We can't tell just by looking at the number.

By analagy pointers are all the same size, 4 bytes. The pointer holds the address of the first bit of memory used to store the address of a variable (or a function). You don't care where the actual physical location of the memory is, as long as you can have access to the information stored there; and you can do that with the memory address stored in the pointer. Knowing the address of the first bit of memory used to store the information in the variable (function) doesn't tell you how much memory is used to hold the information in the variable, it just where the first bit is located. The type information you use when you declare the pointer tells the compiler how much memory will be pointed to, but the pointer itself only holds the address of the first bit.

The way I understand it, every variable and every function you declare is assigned a name and an address by the compiler. That information is kept on the program stack. Then every time you refer to a variable or a function the compiler retrieves the information from the stack to locate the memory address where the information is stored and then get's the information stored in that area of memory to send to the CPU so it can be used in the program.

What's a bit and a byte and how do they figure into memory? Here's my understanding. Memory itself is just some phyiscal entity that can retain its "state" over time. Let's say we're talking about a hard disk. The hard disc may hold 30 gigabytes of information. To make it eaier to find a given spot in that 30 gigabytes worth of memory the disc is formatted; maybe into rings, or sectors, or whatever, it doesn't really matter; much like a city is divided into neighborhoods, or streets, or burroughs, or whatever. Each sector is then broken down into smaller and smaller pieces until you get to a single individual piece of memory called a bit. Each bit can be in only one of two states at a time; say up or down, or on or off, or 0 or 1. The state may be one or the other, but whatever it is it will remain constant until told to change. You can also think of a slightly bigger chunk of memory, say 8 bits at a time, which is called a byte. Each byte can hold up to 256 different cominations of 0 and 1 (corresponding to 2^8). Each unique combination can be thought of as a base ten integer between 0 and 255, inclusive (if you know binary math it is easy to figure how to do this). In turn, each of these unique combinations can be assigned to represent a unique, and arbitrary, character such as a letter, a digit, a punctuation mark or some other item (standard accepted mappings like this include ASCII character set and unicode). Therefore a char is commonly said to take up 1 byte of memory. The int type frequently takes up 4 bytes of memory (although some compilers use other sizes). All the other primitive types take up a given, specified amount of memory, too; and since user declared types can all be traced back to combinations of primitive types, they all have certain, specified "sizes" as well. Again, you don't need to know where any of the actual physical memory is, the OS does this for you. All you need to know is name of the variable or function. The compiler then gets a memory address for the variable/funtion from the OS which is then stored in the program stack until you use it during the program.

Thread: Linked Lists

Thread Tools

Search Thread

Display

Linked Lists

First part is good, But still a little fuzzy

Similar Threads

Linked Lists 101

Map file formats and linked lists

Linked Lists Integer addition ? HELP Please??

need help w/ linked lists

doubly linked lists