Linked List, how to?

[Daffa]

Okay, pretty much I'm new to this LL stuff (all I know well is arrays, not pointers). So, pretty much I need the LL to traverse through a list of data I made according to their key in a specific order.

Here's a code I made. I know it's broken but at least show how far I already get.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node* link;
} node;
struct node* A;
void nodes()
{
    struct node* temp = (struct node*)malloc(sizeof(node));
    (*temp).data = 2;
    (*temp).link = NULL;
    A = temp;
}

int main()
{
    struct node* temp1 = A;
    while (temp1->link != NULL)
    {
        temp1 = temp->link;
        printf("%d\n",temp1->data);
    }
    temp1->link = temp;
    return 0;
}

Aim :

Input :

Data	Key
100	1
50	2
30	3
40	4
25	5

Order of Key :
1-3-2-5-4

Output :
100
30
50
25
40

 

[IcemanBo]

Needs to be C?
I found a old code from first C classes, maybe it helps a bit.
Or you need a doubly linked list?

#include <stdio.h>
#include <stdlib.h>

/*  Data structure - Queue - API    */
  
    struct Queue* NewQueue();
        // Returns a new queue.

    struct Queue* Push(struct Queue* q, const int i);
        // Adds integer i to the back of the queue.
      
    struct Queue* Pop(struct Queue* q);
        // Removed the first element of the queue.

    int IsEmpty(const struct Queue* q);
        // Returns true if the queue is empty.

    void PrintQueue(const struct Queue* q);
        // Prints all elements of the queue within a single line, seperated by a space.
          
    #define MAX_SIZE 20
        // Defines the max size of a queue. Set to "0" for infinite amount of elements.
      
//  =================================================== //

struct Node{
    struct Node* next;
    int element;
};

struct Queue{
  
    struct Node* first;
    struct Node* last;
    int size;
  
};

struct Queue* NewQueue(){
    struct Queue* q;
    q = malloc(sizeof(struct Queue));
    q->first = 0;
    q->last = 0;
    q->size = 0;
    return q;
}

struct Queue* Push(struct Queue* q, const int i){
  
    if(MAX_SIZE && q->size >= MAX_SIZE){
        printf("ERROR - Struct Queue: function Push _ Max size is %d. \n", MAX_SIZE);
        return q;
    }
  
    struct Node* n = malloc(sizeof(struct Node));;
  
    if(!q->size){
        q->first = n;
        q->last = n;
    }
    else{
        q->last->next = n;
        q->last = n;
    }
    q->size++;
    q->last->element = i;
    return q;
}

struct Queue* Pop(struct Queue* q){
    if(q->size){
        q->first = q->first->next;
        q->size--;
    }
    else{
        printf("ERROR - Struct Queue: function Pop _ Queue is empty.\n");
    }
    return q;
}

int IsEmpty(const struct Queue* q){
    return !q->size;
}

void PrintQueue(const struct Queue* q){
    struct Node* n = q->first;
    for(int i = 0; i < q->size ; i++){
        printf("%d ", n->element);
        n = n->next;
      
    }
    printf("\n");
  
}

int main(){
  
    struct Queue* q = NewQueue();
  
    Push(q, 1);
    Push(q, 3);
    Push(q, 5);
  
    PrintQueue(q);
  
    Pop(q);
    PrintQueue(q);
  
    Push(q, 1);
    PrintQueue(q);
  
    return 0;
}

 

[Daffa]

No doubly thanks.

Well, I made the file in C since I haven't learn C++ yet. Maybe about time I switch.

Appreciate the code, I try to understand and implement them myself

 

[Ruke]

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int value;
    struct Node* next;
};

struct Node* create_node(int value) {
    struct Node* node = malloc(sizeof *node);
    node->value = value;
    node->next = NULL;
    return node;
}

void node_set_next(struct Node* node, struct Node* next) {
    node->next = next;
}

int main() {
    struct Node* node1 = create_node(100);
    struct Node* node3 = create_node(30);
    struct Node* node2 = create_node(50);
    struct Node* node5 = create_node(25);
    struct Node* node4 = create_node(40);
 
    struct Node* iterate = node1; // start to iterate from first node
 
    node_set_next(node1, node3); // so node1->next will be node3
    node_set_next(node3, node2);
    node_set_next(node2, node5);
    node_set_next(node5, node4);
 
    while (iterate) { // while iterate is not null...
        printf("Hello, I'm storing value %d!\n", iterate->value);
        iterate = iterate->next; // advance to the next node
    }

    return 0;
}

 

[Daffa]

Thanks, I'll take a look into the code, seems easy enough by the looks of it.

Truly appreciate help from you guys, @Ruke, @IcemanBo

 

[IcemanBo]

Ah ok, I also found something with normal list with only add and remove.

#include <iostream>
using namespace std;

class Node{
public:
    Node* next;
    Node* prev;
    int element;
};

class List{
public:
    Node* head;
    int size;
   
    List(){
        size = 0;
        head = 0;
    }
   
    List* add(int i){
        Node* n = new(Node);
        n->element = i;
     
        if(!head){
            head = n;
            n->next = 0;
            n->prev = 0;
            return this;
        }
       
        n->prev = head;
        n->next = 0;
        head->next = n;
        head = n;
       
        return this;
       
    }
   
    List* remove(Node* n){
        if(n->prev && n->next){
            n->prev->next = n->next;
            n->next->prev = n->prev;
           
        }  
        else if(n == head){
            head = n->prev;
           
        }
           
        else{
             n->next->prev = 0;
             
        } 
        free(n);
        return this;
    }

};

void printList(List* l){
    cout << "<List>" << endl;
    for(Node* n = l->head; n ; n = n->prev){
        cout << n->element << " ";
    }
    cout << endl << "</List>" << endl;
}

int main()
{
  List* l = new(List);
  l->add(3)->add(5)->add(7)->add(91)->add(0)->add(-3);
  printList(l);
 
  return 0;
}

btw, it was @Ruke not Rufus. ;D

 

[Daffa]

Thanks @IcemanBo. Oh my, I guess my eyes deceive me. Sorry @Ruke, and thanks for the help.

 

[Rufus]

I AM SUMMONED!

Oh... Not needed though.
I guess I'll take my leave then. </3

 

[Dr Super Good]

C++ should come with a standard generic linked list implementation as well as appropriate means to iterate through it. Outside of academic exercises or extreme optimization I would recommend using this implementation over your own.

IcemanBo, technically a size field is not needed for a linked list, although it is sometimes worth it due to performance benefits it can bring. A simple linked list could consist of nothing more than a pointer to a head node, with no containing object type.

Also one should not assign a pointer to 0 as 0 is a number and not an address, rather use NULL or one of its other portable aliases even if they end up evaluating to a numeric 0. This is mostly for readability as it makes it clear that pointers are involved and not numbers.

 

[IcemanBo]

Sure, the size was just needed back then.

 

[Aniki]

all I know well is arrays, not pointers

Fair enough:

#include <stdio.h>
#include <stdlib.h>

const int /*JASS*/C_MAX_ARRAY_SIZE = /*8192*/ 1 << 13;

struct kv {
    int key;
    int value;

    int prev;
    int next;
};
kv List[C_MAX_ARRAY_SIZE];
int next_node = 0;
int fl_head = 0;

int make_node(int key, int value) {
    int self;

    if (fl_head == 0) {
        if (next_node + 1 >= C_MAX_ARRAY_SIZE) {
            printf("can't make a new node, sorry!!! our arrays can only go up to %d "
                "but you shouldn't really try to access their %d index or you "
                "won't be able to load your savegames, sorry about that too\n",
                C_MAX_ARRAY_SIZE, C_MAX_ARRAY_SIZE - 1);
            exit(8192);
        }
        next_node += 1;

        self = next_node;
    }
    else {
        self = fl_head;
        fl_head = List[fl_head].next;
    }

    List[self].key = key;
    List[self].value = value;
    List[self].prev = self;
    List[self].next = self;

    return self;
}

void destroy_node(int node) {
    List[List[node].prev].next = List[node].next;
    List[List[node].next].prev = List[node].prev;

    List[node].next = fl_head;
    fl_head = node;
}

void list_push(int sentinel, int node) {
    List[node].prev = List[sentinel].prev;
    List[node].next = sentinel;
    List[List[node].prev].next = node;
    List[List[node].next].prev = node;
}

int list_find_node_with_key(int sentinel, int key) {
    for (int node = List[sentinel].next; node != sentinel; node = List[node].next) {
        if (List[node].key == key) {
            return node;
        }
    }
    return 0;
}

int
main() {
    int list = make_node(0, 0);

    list_push(list, make_node(1, 100));
    list_push(list, make_node(2, 50));
    list_push(list, make_node(3, 30));
    list_push(list, make_node(4, 40));
    list_push(list, make_node(5, 25));

    int key_order[] = {1, 3, 2, 5, 4, 69105};
    for (int i = 0; i < sizeof(key_order) / sizeof(int); i += 1) {
        int key = key_order[i];

        int node = list_find_node_with_key(list, key);
        if (node == 0) {
            printf("key %d is missing from our list\n", key);
        }
        else {
            printf("key(%d) => value(%d)\n", key, List[node].value);
        }
    }

    for (int node = List[list].next; node != list;) {
        int next = List[node].next;
        destroy_node(node);
        node = next;
    }

    return 0;
}

 

[Daffa]

Well, tbh I can't bare the complication. Guess I wasn't prepared at all

Anyway, I wonder if it's possible for example I linked the list not by struct but by value inside the struct.

Example :
I want the struct to go in order from 8,9,10,12

The structs are :
value;key
8;1
10;2
12;3
9;4

Is it possible for me to link them using the value or key instead of linking the structs?

To be honest, I understand @Ruke 's method the most atm. I appreciate the helps but please bare with my weak understanding of the complex struct and pointer in C. I'll try my best to understand.

EDIT :
@Aniki 's solution seems to offer such thing, though I need to learn more about it before implementing it along with @Ruke 's method.

 

[IcemanBo]

Look for c++ vector in std library, it might be what you want. There are good example in the internet for this.
A vector is a data structure similar like for example lists, but instead of refering to nodes you also can use normal "array api".

For example:

int main() {
    // declare a vector of type "int"
    std::vector <int> myVector;

    // fill vector with using vector API e.g:
    myVector.push_back (10);

    // you can read like array
    std::cout << myVector[0];
}

it's not a good idea to use the value as key, because there can be multiple entries with the same value.

 

[Daffa]

Well, that's something interesting. Can this vector library used in standard C?

 

[IcemanBo]

No, not directly, but the functionaltiy could be mimiced. There are probably templates already out there in google, but the syntax would be not so neat probably.

 

[Ruke]

If the keys are incremental (such as 1, 2, 3... and so on) and you know how many elements you need to store, you can simply use an array:

#include <stdio.h>

int main() {
    int data[5];
   
    int firstKey = 1;
    int lastKey = sizeof(data) / sizeof(data[0]); // or 5, this expression gives you the length of the array
    int iterateKey = firstKey; // iterate from first key
   
    data[1] = 8;
    data[2] = 10;
    data[3] = 12;
    data[4] = 9;
   
    while (iterateKey < lastKey) {
        printf("Hi, my value is %d\n", data[iterateKey]);
        iterateKey = iterateKey + 1; // advance to the next element
    }
}

 

[GhostWolf]

What do you not understand about linked lists? do you know how pointers work in general? because that's all a linked list is - a pointer pointing to a pointer pointing to a pointer and so on.

Your inputs/outputs don't actually require a linked list to begin with. Is there a specific reason you want to use one?

 

[Dr Super Good]

Is it possible for me to link them using the value or key instead of linking the structs?

Yes it is completely possible. You will need to implement a handle table for this that redirects from struct identity number to a struct reference/pointer. This is basically what Java does for objects, where each object is given a unique identity number and the JVM can use that identity number to locate the object in memory without the program knowing where/how in memory an object is.

A vector/array list would work for such a table as long as you recycle the indices of destroyed structs.

 

[Daffa]

What do you not understand about linked lists? do you know how pointers work in general? because that's all a linked list is - a pointer pointing to a pointer pointing to a pointer and so on.

Your inputs/outputs don't actually require a linked list to begin with. Is there a specific reason you want to use one?

Well, if that's the case, then there's nothing more to it. I am not fully aware of pointers capabilities tbh.

Well, I do aware a simple array does the job well. It's just that it's mandatory for the lesson I'm taking now.

@Dr Super Good
Thanks for the insight.

 

[GhostWolf]

Well, a pointer just...well, points to some location in memory.
In the case of a linked list, you have all of your nodes allocated separately, which might mean they are located in arbitrary locations in memory.
Each node then stores the location of the next one.
So in the end you have a list of objects, but they are not necessarily consecutive in memory like an array, which is why you can't iterate using indices.

typedef struct Node {
    struct Node *next; // will be the location of the next node
    void *data; // or whatever kind of data you want
} Node;

// in main or whatever

Node *head = (Node*)malloc(sizeof(Node)); // allocates the size of two pointers, so 8 bytes on 32bit machine, 16 bytes on 64bit machine.
Node *node2 = (Node*)malloc(sizeof(Node));

head->next = node2; // now we have a list head->node2
node2->next = NULL; // very important! must null unused pointers

// now to iterate over the list
Node *node = head;
while (node != NULL) { // != NULL can be dropped, left it here for clarity
    // do stuff

    // move to the next node in the list
    node = node->next;
}

As you can see, there are two Node objects allocated, and their addresses are stored in variables, as usual.
The first one's next field is then set to the next node.
It's very important to set the next field of the last node to NULL, as with any unused pointer!

Obviously, for cleanness, you'll want to make some LinkedList (or whatever) struct, and add functions to add/remove/search/iterate/whatever nodes to it, which will essentially look like the above.

If you want generic nodes, you can use a void pointer like the above. In this case, you'll need to also add some way to identify the type of node it is (which can be done in many ways). If you only need something specific, like you do in your case, just put your data there directly.

And as you can probably easily see, this is the same as what Ruke wrote, and the same as all of the other examples here that implement a linked list, because there's no way to be tricky with linked lists, they are too compact - just a pointer pointing to a pointer pointing to a pointer etc.

 

[Daffa]

@GhostWolf

I truly appreciate the help. It helps me understand the code much better now.

So, as far as I can see, there's no way to make it more efficient than what already is done. Guess readibility is the only difference I could make. Thanks.