|
Chris
|
Linked Lists
 Posted: Sun Mar 05, 2000 2:42 am
|
How exactly does a linked-list work?
Chris :o)
|
|
Eric
|
Posted: Sun Mar 05, 2000 8:45 pm
|
Quote > How exactly does a linked-list work?
> Chris :o)
The following discussion assumes you know what the following terms mean with respect to C/C++:
POINTER
ARRAY
STRUCT
A linked list is a simple data structure. The list consists of nodes, each of which contains some data, and a link to the next node. To implement a linked list, you need to define a STRUCTURE to represent the node. The STRUCTURE contains at least two fields: one field is the data for the node, and the other field is a POINTER to a the node structure.
Here's a simple node definition:
struct Node
{
int Data;
Node* Link;
};
To declare a node:
Node HeadNode;
To create a list, simply create nodes and set the LINK pointer of each one to the next node in the list. Normally, you would create INSERT and DELETE functions to add or remove nodes from the list. The benefit of using linked lists is that the size of the list can change dynamically simply by adding or removing nodes. Furthermore, if you know how to use malloc (or new in C++) you can dynamically allocate memory for the list by creating nodes only when you need them, this can greatly reduce your program's memory requirements. Another benefit of the link list is that nodes can be removed from the middle of the list. Contrast a linked list to an ARRAY which is a fixed size, and elements can't simply be inserted or removed without shifting the remaing elements down.
One drawback of linked lists is that you can't access a node directly, you can only start from the HEAD of the list and search through each one until you find the node you need.
I've only explained the very basics of what a linked-list is, there are a LOT of subtleties to implementing one, though. I recommend picking up a programming book about data structures to help you, or e-mail me directly if you have specific questions.
Good luck.
Eric Quinn
|
