CODEWITHSUNDEEP
pythonccython
Braiden Gole
Braiden Gole

Reputation: 175

Cython Doubly Linked list printing in order

Hi I am building a doubly linked list structure I am looking to print my test names/words in alphabetical order.

The final product should look like this:

BRAIDEN
BRANT
DAVE
KIM

Currently show_all will display the last entry copied over all previous entries.

Example: If "DAVE" was entered in last all the output would be:

DAVE
DAVE
DAVE
DAVE

If I print within the create() function I get the output:

BRAIDEN
BRANT
KIM
DAVE

which is not alphabetical order but rather the order I entered them in.

Note: my doubly linked list as of now does not seem to be printing through its structure. What I mean is you could just simply print the nodes or call show_all either way as of right now it is not printing through the structure it is as if they are being printed individually.

Program.pyx

from libc.stdlib cimport malloc, free

cdef struct Node
cdef struct Node:
    char* word
    Node* prev
    Node* next

cdef class DoublyLinkedList:

    cdef Node* head
    cdef Node* tail
    cdef Node* last_node
    cdef Node* next_node

    def __cinit__(self):
        self.head = NULL
        self.tail = NULL
        self.last_node = NULL
        self.next_node = NULL

    def create(self, word):
        cdef Node* new_node = <Node*>malloc(sizeof(Node*))
        if not new_node:
            raise MemoryError()

        new_node.word = word
        new_node.prev = NULL
        new_node.next = NULL

        if (self.head == NULL):
            self.head = new_node
            self.tail = new_node
        elif (self.head.word >= new_node.word):
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        else:

            last_node = self.head
            next_node = self.head.next
            while (next_node != NULL):
                if (next_node.word >= new_node.word):
                    break
                last_node = next_node
                next_node = next_node.next

            new_node.prev = last_node
            new_node.next = next_node
            last_node.next = new_node

        if (next_node == NULL):
            self.tail = new_node
        else:
            next_node.prev = new_node
    
    def show_all(self):
        while (self.head != NULL):
            print(self.head.word)
            self.head = self.head.next

testing_interface.py

import program

algo = program.DoublyLinkedList()

algo.create(bytes("BRAIDEN", encoding="utf-8"))
algo.create(bytes("BRANT", encoding="utf-8"))
algo.create(bytes("KIM", encoding="utf-8"))
algo.create(bytes("DAVE", encoding="utf-8"))
algo.show_all()

Upvotes: 1

Views: 78

Answers (2)

DavidW
DavidW

Reputation: 30928

node.word does not own it's own memory. It points into memory owned by a Python bytes object. That memory is valid only as long as the bytes object is alive.

Since you initialize it with a temporary that is passed to the constructor the memory is only valid for the duration of the constructor and no longer.

You either need to keep the bytes objects alive, or copy they contents into memory that you manage.

Upvotes: 2

MikeCAT
MikeCAT

Reputation: 75062

You should allocate for one node, not for one pointer, to allocate a node.

In other words, the line

cdef Node* new_node = <Node*>malloc(sizeof(Node*))

should be

cdef Node* new_node = <Node*>malloc(sizeof(Node))

Upvotes: 0

Related Questions