One of the big advantages of arrays is that you can allocate memory for a large number of variables without writing a lot of code. It's also simple to initialize or change their values 'all at once' with a while or for loop. However, the big disadvantage of using an array is that you may not always know exactly how many items you will need to store. You may be reading in data from a file, and you won't necessarily know how big to make your array. Another problem with arrays is that rearranging elements in the array can be time consuming. Suppose you have 100 elements in an array and you decide that you want the 100th element to be the second element and the second to be the third and the third to be the fourth and so on. You'll have to 'shift' all the elements down one place. This is not very efficient.A linked list can change size as the program runs, and items can be inserted into the middle of the list without causing the other elements to change their locations in memory. Writing linked list code is more complicated than using arrays, but for many applications using a linked list instead of an array is much more efficient. A linked list consists of structs, one per element in the list. Each element on the list is often referred to as a 'node'. Besides storing the necessary data, each struct will also have an element which is a pointer. The pointer will have the value of the address of the next node in the list. It is these pointers which makes the list linked (instead of just a bunch of seperate structs.)
The syntax for declaring a simple linked list is:typedef struct node *link; struct node { int data; link next; };The words in italics are all variable names that I made up. Although 'node', 'link', and 'next' are all names that are commonly used, there is nothing special about them. They could easily be called a,b, and c (but of course, you wouldn't want to give your variables such 'un-descriptive' names!) Also, 'int data' is arbitrary. This linked list is set up to hold integers. You might want to build a linked list that holds points or Rationals or any other data you can think of.
The first line defines the 'link' type of pointer. Whenever you want to access a node on your list, you will use a pointer of type link. Each node on the list has one pointer of type link (called next.) Whenever a node is added to the list, we'll attach it to the list by setting the value 'next' part of the struct to the address of that new node.
To create a new node (with the definition given above), you write:link x = malloc (sizeof *x);malloc is a function which allocates memory. Its argument is the amount of memory to be allocated. In this case, we want to allocate enough memory for a node. The sizeof operator will return the size of the data type it precedes. Here, we want to allocate enough memory for a node (or 'the thing x points to', which is a node.) The value returned by malloc will be NULL if there is no memory available. NULL is just a constant with value 0. If you set a pointer to NULL, you are saying that the pointer does not point to anything. If there is available memory, the pointer 'x' will be given the value of the address of the newly allocated memory. So, x 'points' to this new node. Notice that this node doesn't have a name of its own. We access it by its address (just as we access an element of an array by its address, or offset from the beginning of the array.)
NOTE: It is a common mistake to 'abuse' malloc. You should only use malloc when you want to create a new node!!! Do not use it for any other purpose.
When you no longer need the node anymore (usually because you are deleting an element from the linked list), you can use 'free' to return the memory used by the node to the system. The syntax is:
free(x);Just pass the address of the node you are deleting to free.
Here is some basic linked list code. It's a good idea to draw pictures when you're trying to understand linked list code. Generally, you can draw a box for each node and an arrow going from each node to the next to represent the 'next' pointer.
--- THE REST OF THIS PAGE IS COMING SOON --- SORRY FOR THE INCONVENIENCE!! ---