Author : Shadow Mint
Page : << Previous 2
we get the object after the one we want to remove;
temp3 = temp.next;
// Now rebind the chain, the next pointer now points to telnet.exe
(windows.exe).next = temp2;
// And replace the null pointer in telnet.exe by pointing it to the
// "old" directory
temp2.next = temp3;
// Finally we finish the chain by making the "old" directory point back to
// the telnet.exe, rather than the now deleted object.
temp3 = temp2;
Or in short form, get rid of the temporary variables:
(windows.exe).next.next.prev = (windows.exe).next.dir;
(windows.exe).next.dir.prev = (windows.exe);
(windows.exe).next.dir.next = (windows.exe).next.next;
(windows.exe).next = (windows.exe).next.dir;
This might be confusing; but it just cuts out the temps. For easy of reading and understanding code; either a) comment vigourly in your code, or b) use some kind of temporary variable.
These two examples should demonstrate the basic workings of a linked list. From here, lets move on to develop a generic class (a simple one mind you, but none the less), for holding a linked list. To start with, we need to choose what manipulators we want for the list. For example:
* add element (n)
* remove element (n)
* empty list
* create base object
* fetch element (n)
* set element (n)
These six basic manipulations allow for all the functionality you might want from a simple linked list. We could now go and implement that in c++, or java. However, since I don't particularly like c++, and java automatically handles memory, we'll settle for stand c for this example (which may be more complicated, but so be it).
We start by creating a class structure, to hold these manipulations, along with the base object.
typedef struct
{
} LLClass;
Now we need contents: for this, we're going to need seven basic items: pointers to hold the functions which will perform these tasks, and the base element pointer for the class. Since we want to be generic, we'll have to make some kind of generic structure for the base element as well:
struct LinkST
{
long ID;
void *data;
struct LinkST *next;
struct LinkST *prev;
}
// ...and just typedef it for easy reference.
typedef struct LinkST LinkTD;
This is a very basic link structure; all it contains is an identifier, a pointer for the data and two pointers for the links (this is a duel link linked list).
So for our LLClass we'll have:
// The base object
LinkTD *baseobj;
// Add an empty element
LinkTD *(* add_element) (LLClass *class, int n);
// Remove an element
int (* remove_element) (LLClass *class, int n);
// Free the list
int (* empty_list) (LLClass *class, );
// Create the base object
LinkTD (* create_list) (LLClass *class, );
// Set element n to element
int (* set_element) (LLClass *class, LinkTD *element, int n);
// Return element n
LinkTD *(* fetch_element) (LLClass *class, int n);
Now, when ever we create a new LLClass, we're going to have to set the values in it. We'll do this in some simple function like: initLLClass (), which simply sets the pointers for all of the functions (eg. myList.empty_list = (* empty_list);). Note how each of the function also takes an LLClass argument. Since the functions need to access the items in the class, they need to have access to the class. Thus running a function should be something along the lines of:
(* myClass.set_element) (myClass, new_val,-1);
(Note: If you've never learnt how to do pointers to functions this may be slightly difficult to understand. Look it up; many places on the net cover this topic)
I'm not going to go through the code for these functions, only a basic algorithm for each one. It is important to check each time, that the base object is not null, because if it is, any attempt to access it will cause a fault. In general, the functions return 1 on happy completion, and 0 on failure; unless they return a pointer, in which case NULL is returned on failure. Make special note of the empty list function! This is very important to avoid memory leaks in.
* add element (n)
return value = 0
if (class.baseobj != NULL)
goto the nth element
calloc one new LinkTD (so all values default to 0)
connect links
return value = pointer to new object
end-if
return the return value
* remove element (n)
return value = 0
if (class.baseobj != NULL)
goto the nth element
temporary = point to that element
connect links on adjacent objects
free temporary
return value = 1
end-if
return the return value
* empty list
return value = 0
if (class.baseobj != NULL)
goto the last element
move back to the first element, freeing each next element
free the baseobj
baseobj = NULL
return value = 1
end-if
return the return value
* create base object
return value = 0
// Here we make the opposite check, since a massive memory leak will
// occur if the baseobj is not null when a new one is created
if (class.baseobj == NULL)
calloc one new LinkTD (so all values default to 0)
baseobj = pointer to new object
return value = pointer to new object
end-if
return the return value
* fetch element (n)
return value = 0
if (class.baseobj != NULL)
goto element n
return value = pointer to that element
end-if
return the return value
* set element (n)
return value = 0
if (class.baseobj != NULL)
goto element (n - 1)
temporary = pointer to next element
next pointer of this element = insertion element
reconnect links
return value = 1
end-if
return the return value
Finally, note that we could also add functionality to sort the list and search the list using the identifier... there are also a huge number of other possibilities for things to do. Generally, every linked list is different. With any luck, this articles has given an understandable introduction into how they work. Good luck in doing what ever it is you do. =)
...and I must apologise for not making the full source avaliable for these algrothims, as I implemented them, but my exams are keeping me kinda tied up. Sorry.
Page : << Previous 2