Nodes of Abstract Data Type in C Programming

ADT(abstract data type)

ADT covered in the leccture:

• linked list
  • pointer based
  • array based

Structure contains a struct head pointer(has size info inside), and serverl pointers as
node(has element info inside).
Can also use array for sort, but not recommended, since is a big waste of memory, and size is
hard to change.
A very basic data storage type, can be straight forward or circle(last node points to head),
even loop inside(e.g. last points to the second node)

• stack
  • pointer based

LIFO properties, useful in check if the input has two exactly same expectations

• set
  • array based

Can compute the union, intersection of it, but since it is array based, it is hard to modify
the length.

Interesting question of ADT

delete a node in linked list

Basic ideal: declare two pointer in the stack memory. One call destroyer, directly point to the
data structure and destroy the node. Another called cacher, saving the info in the pointer
inside the structure.
Operation order: cacher points to the structure before the TGT(target) structure, points to the
pointer inside.
cacher first linked the pointer inside TGT to the pointer of where cacher points to.
then destroyer remove the TGT node.
(Interesting fact here: free() function will remove everything inside the structure, including
pointer inside structure)

Here, construct a structure pointer called destroyer, points to the TGT, node to be
deleted.
What happen during this process? let’s dive into it.
First, TGT is a pointer. This pointer points somewhere in the heap area of RAM. TGT
just store the address info of this node.
Now a pointer called destroyer holds the same address of this node. So modification
through destroyer will affaect on this node, same for TGT.

Interesting Points: Consider below code.

destroyer = TGT;
TGT->next = another_node;
return destroyer->next;

What does this code return? Red one or Red two?
The answer is red two.

This happens when you want to use destroyer to store some info of a node pointer. What
you can store is only the address of the node. As for the pointer inside the node, it can
be modify, and might already change when you call destroyer.

Another Interesting Points: Accessing the pointer inside structure
It is useful to access the pointer inside a structure via a pointer, which points to this
structure.
Directly modify the Node->next will always cause inconvenience.

Locating the middle element in linked list

node number is unknow

• brute locate: travel all node to get number, then travel to number/2
• turtle vs rabbit: struct two pointer inside stack, one travel two node while another just
  travel one node.
  When the fast one reach a NULL, stop and return the slow one

Judge a linked list circle or not

struct a pointer inside stack, judge if it will equal to the head pointer or not.
One interesting fact here is when you want to link a list to a circle, you need to modify the
pointer inside the structure. It can easily be done by modifying using
Structure->pointer_to_next. But do not use a pointer directly point to pointer inside
structure, since it cannot modify the pointer inside strucutre.