0
typedef struct NodeStruct NODE;
typedef struct ListStruct LIST; 

struct NodeStruct {
  void *item;
  NODE *previous;
  NODE *next;
  int location;
};

struct ListStruct {
  int ListSize;
  NODE *HeadNode;
  NODE *CurrentNode;
  NODE *TailNode;
  NODE NodeArray[MaxNode];
};

NODE *HeadArray[MaxHead];
static int HeadCount = -1;
int HeadCurrent = 0;
int i;

Fairly new at C, sorry to sound so very inexperienced ahead of time...

I would like to implement the LIST abstract data type without the use of malloc() or free(), so by storing the nodes in statically allocated arrays. Each list element is a NODE, and can hold one "item". I need to be able to traverse through the nodes using next and previous, and have the notion of "current", "tail", "head".

There are also two arrays... One array of pointers to the "heads", and so then for each head, there is an array of "nodes". I also need to be able to change the current item to one anywhere the middle (or front or end) of the list, be able to delete that node, and then somehow (this is the most confusing part to me) be able to use that spot in the array again, BUT, I can't traverse through the list to find a 'free' node because that's not efficient.

I also need to do the same thing for the "head" array, so, there is a notion of max number of lists (which would mean the head array is full), and I also need to be able to delete an entire array of nodes, (which in turn, means I have to be able to delete a head node from that list as well and somehow be able to put one back there if i need that space).

Problem is I've had a horribly awful time trying to implement this! The above code is the structure I have been working with so far, and I've tried two different ideas:

1: Every time we "remove" a node from the array (which as far as I'm concerned is just setting it's ITEM to NULL and switching it's connected nodes nexts' and previous' to each other), we move the rightmost node in the array to this spot. When we add a new node, we always add it to that spot. So, no searching, but absolutely a nightmare to implement (in my experience).

2: Have a separate list (stack) of "free nodes", which I can take from when I need a new one. However, this means that I'd have to create all those nodes initially and maybe not use them which would not be good memory-wise.

What I would really like to do, and can't figure out, is as follows:

For the "heads" array: we have an array of pointers which points to the "head" of each node. For the each "heads" we have, initially, an empty array of nodes. For each empty array of nodes, we also have a list of "free" pointers, which are pointers to each free spot in the array, and when we insert a new item, we take the top address of this pointer array and that's where the new node will be placed in the node array. When we delete from the node array, we place that nodes address on top of the stack.

However, I'm stuck on what ListCreate will look like, because that's just an empty array of nodes, and the head array won't actually be pointing to anything then.

These are the specifications of what I'm working on so I can't change the requirements too much. ie, i can't not have an array of head pointers.

Any ideas on how I can implement this efficiently and to these requirements? I just need help setting up the structures and what 'list create' will look like, and the general idea behind the manipulation of the nodes. I can figure all else out hopefully. I'm just really stuck on a general, efficient idea.

Any help is appreciated. Thank you.

Zakir
  • 2,222
  • 21
  • 31
Aero
  • 1
  • 1
  • This does not make any sense. You need to choose: do you want a linked list or a dynamic array. – Jazzwave06 May 31 '17 at 20:04
  • can you post exact initial requirements, not your interpretation of them? – Iłya Bursov May 31 '17 at 20:07
  • If you want us to help debug code, then present code. We generally expect one *specific*, narrowly-focused question, backed by a [mcve]. – John Bollinger May 31 '17 at 20:11
  • If you want a statically allocated array of nodes, you can use two linked lists. One of used nodes, one of available nodes. When you free a node, you remove it from the active linked list, and add it to the head of the available linked list. When you want a new node, take it from the head of the available list. It's a bit more complex that that, but there is the basic idea. Moreover you can work with array indices instead of pointers. – Weather Vane May 31 '17 at 20:14
  • Overall, though, if you want to avoid dynamically allocating `NODE`s, then you have no alternative to declaring all the nodes you could ever need statically, presumably as the elements of an array. You will then need to track which are used and which are available. Your options (1) and (2) are just different variations on this theme, and yes, such approaches have substantial overhead. Also, they impose a hard limit on the program's item capacity. – John Bollinger May 31 '17 at 20:17
  • You could still dynamically `malloc` the array of available nodes to start with. I skimped a bit; if there are no nodes in the "available" linked list, you take the next unused one from the pre-allocated array. If there are no nodes there, you `realloc`a bunch more. This technique saves time over continual `malloc` and `free` operations for individual nodes. – Weather Vane May 31 '17 at 20:20
  • see http://stackoverflow.com/a/39618642/905902 for an example of creating lists and trees in statically allocated space. [note: this is *not* trivial, and might be too difficult for novice C-programmers] – wildplasser May 31 '17 at 20:50
  • [What is the XY problem?](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem) ... and why is your question full of them? – autistic Jun 01 '17 at 00:04
  • [What is premature optimisation?](https://stackoverflow.com/questions/385506/when-is-optimisation-premature) ... and why do you think your attempts at optimisation are *premature*? – autistic Jun 01 '17 at 00:14

1 Answers1

0

If you're going to use an array of pointers to nodes for each list, I don't see the need for using linked list concepts like previous and next pointers in the nodes, and instead the code could be array oriented.

The question states that removing a node is done by replacing the node to be removed with the last node in the array, so the array order is not preserved. I assume that adding a node is done by appending a node to the end of an array.

Each array structure could have a count of elements, index to current element, and array of pointers.

There could be one structure for the free pool of elements (statically allocated), the rest of the structures would initially be empty (count == 0). Elements would be removed from or added to the end of the array of pointers for the free pool, similar to a stack.

The item information could be included in the element structure as opposed to being handled via a pointer in the element structure.

The logic for removing a node from the current position:

    free[count] = list[current];
    free.count++;
    list.count--;
    if(list.count != 0)
        list[current] = list[count];

The logic for appending a node:

    if(free.count != 0){
        free.count--;
        list[count] = free[count];
        list.count++;
    }
rcgldr
  • 27,407
  • 3
  • 36
  • 61