Index · Preferences · Help
Announcements · BYOND Discussion · Bug Reports · Developer How-To · Code Problems · Design Philosophy · Creations · Classified Ads · Gaming · Computers & Technology · Community
Forum Search:

[Advanced Search]

[Messages in this Thread] [Show All (5)]    [Archived Thread] [Return to Design Philosophy]

Author:Theodis [Posts]
Date:4/27/05 4:07 am
Topic:Re: Programmer Giving Free Services
Post ID:347289
Parent ID:347281
> I also happen to not know what linked lists are. Nor pointers.

A pointer is a simple concept of having a variable store the address of another :P.

Anyway a linked list is a list but rather than allocating a chunk of memory like you would with an array you just build it one item at a time. Each item has a reference/pointer to the next item in the list and the last one points to null(so you know it is the end).

A basic implementation of one is

LinkedListNode
  var/data
  var/LinkedListNode/next
  New(d)
    data = d
    next = null
  proc/Count
    . = 0;
    for(var/LinkedListNode/i = src; i.next; i = i.next)
      .++;
  proc/Add(d)
    var/LinkedListNode/i = src
    //Find the last node in the list
    while(i.next)
      i = i.next
    //Add in the new node
    i.next = new(d)
    return i.next

Then to use one simply make a head node(and in this case it should have data. Here's an example.

proc/SomeProc()
  var/LinkedListNode/head = new(0)
  //Fill up the linked list with the numbers 0 to 9.
  for(int i = 1; i < 10; i++)
    head.Add(i)
  //Output them
  for(var/LinkedListNode/i = head; i.next; i = i.next)
    world << i.data

This is the basic idea of how to make and use one. I didn't include a remove proc because removing items is slightly tricky and I wouldn't want to try and get it right off the top off my head without testing.

Though in DM you probably will never use a linked list unless it is part of a different data structure like a tree or a queue since most of its bonuses really don't apply though the downsides do. The main bonuses of linked lists is that it is dynamic in size(with an array you have to create a new one and copy over the old contents to adjust size) and you don't need to allocate a contiguous chunk of memory(in C if you allocate a large array all the memory has to be in one large block or you'll get an error when trying to make a new array even if you have lots of free fragmented memory). Of course the fact that you are allocating memory in arbitrary locations is the type of thing that leads to memory fragmentation quickly. The downside to a linked list is that you no longer have random access so if you want to get to the fifth element in the list you have to go through all the nodes before it to get to it. In my example this applies when adding an item(and removing if I added it) along with counting size.

Though as I noted for a queue this isn't really a problem as you can keep a reference to the head and tail and since you aren't supposed to iterate througha queue random access isn't an issue. Removing the head is quite trivial just do
head = head.next and boom now the head item is the second one in the list and you didn't have to move any of the other nodes to maitain the structure of the list. To add an item you simply do tail = tail.Add(newitem) and you add in an item without iterating through the list.

And now since I've went through the process of writing the LinkedList code here is a Queue using one :P.
Queue
  var/LinkedListNode/head
  var/LinkedListNode/tail

  New()
    head = null
    tail = null
  proc/Enqueue(d)
    if(!tail)
      //If there is no tail but a head something got corrupted
      ASSERT(!head)
      if(!head)
        head = new(d)
        tail = head
    else
      tail = tail.Add(d)
  proc/Dequeue()
    ASSERT(head)
    . = head.data
    head = head.next
    //If there is no head ensure there is no tail either
    if(!head)
      tail = null
  proc/IsEmpty()
    return head != null

LinkedListNode
  var/data
  var/LinkedListNode/next
  New(d)
    data = d
    next = null
  proc/Count
    . = 0;
    for(var/LinkedListNode/i = src; i.next; i = i.next)
      .++;
  proc/Add(d)
    var/LinkedListNode/i = src
    //Find the last node in the list
    while(i.next)
      i = i.next
    //Add in the new node
    i.next = new(d)
    return i.next

Maybe once my finals week is over I should find some time to write some tutorials on this type of stuff :P.

Messages in this Thread: [Show All (5)]

  What is a stack and a queue? Jp (4/27/05 1:23 am)
      Re: Programmer Giving Free Services Theodis (4/27/05 2:01 am)
          Re: Programmer Giving Free Services Jp (4/27/05 2:43 am)
              Re: Programmer Giving Free Services Lummox JR (4/27/05 2:04 pm)
              Re: Programmer Giving Free Services Theodis (4/27/05 4:07 am)