# 2022q1 Homework1 (lab0)
contributed by < [Build-A-Moat](https://github.com/Build-A-Moat/lab0-c) >
###### tags: `linux2022`
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i7-4720HQ CPU @ 2.60GHz
Stepping: 3
CPU MHz: 2320.005
CPU max MHz: 3600.0000
CPU min MHz: 800.0000
BogoMIPS: 5187.67
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/linux2022-lab0)
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作,需要由學員補完並逐步精進,包含以下:
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* `q_release_element`: 釋放特定節點的記憶體空間;
* `q_size`: 計算目前佇列的節點總量;
* `q_delete_mid`: 移走佇列中間的節點,詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* `q_delete_dup`: 在已經排序的狀況,移走佇列中具備重複內容的節點,詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* `q_swap`: 交換佇列中鄰近的節點,詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* `q_reverse`: 以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列節點,換言之,它只能重排已經存在的節點;
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點,可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
## 開發過程
### q_new
* Create empty queue.
* Return NULL if could not allocate space.
```c
struct list_head *q_new()
{
struct list_head *queue = malloc(sizeof(struct list_head));
if (queue)
INIT_LIST_HEAD(queue);
return queue;
}
```
### q_free
* Free all storage used by queue
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *node, *safe;
list_for_each_entry_safe (node, safe, l, list) {
q_release_element(node);
}
free(l);
}
```
Use `list_for_each_entry_safe` rather than `list_for_each_entry` because node will be delete, and safe will keep node->next before delete.
Use `list_for_each_entry_safe` rather than `list_for_each_safe` because node `queue.c` provides `q_release_element` .
### q_insert_head
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
element->value = strdup(s);
if (!element->value) {
free(element);
return false;
}
list_add(&element->list, head);
return true;
}
```
### q_insert_tail
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
element->value = strdup(s);
if (!element->value) {
free(element);
return false;
}
list_add_tail(&element->list, head);
return true;
}
```
### q_remove_head
* Attempt to remove element from head of queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *remove = list_first_entry(head, element_t, list);
list_del(head->next);
if (sp) {
strncpy(sp, remove->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return remove;
}
```
### q_remove_tail
* Attempt to remove element from tail of queue.
* Other attribute is as same as q_remove_head.
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *remove = list_last_entry(head, element_t, list);
list_del(head->prev);
if (sp) {
strncpy(sp, remove->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return remove;
}
```
### q_release_element
* WARN: This is for external usage, don't modify it
* Attempt to release element.
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_size
* Return number of elements in queue.
* Return 0 if q is NULL or empty
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int count = 0;
struct list_head *node;
list_for_each (node, head) {
count++;
}
return count;
}
```
### q_delete_mid
* Delete the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return true if successful.
* Return false if list is NULL or empty.
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *slow = head, *fast = head;
while (fast->next != head && fast->next->next != head) {
slow = slow->next;
fast = fast->next->next;
}
struct list_head *middle = slow->next;
list_del(middle);
q_release_element(list_entry(middle, element_t, list));
return true;
}
```
`list_del` only `remove` node from list but `q_release_element` can `delete` node
### q_delete_dup
* Delete all nodes that have duplicate string,
* leaving only distinct strings from the original list.
* Return true if successful.
* Return false if list is NULL.
* Note: this function always be called after sorting, in other words, list is guaranteed to be sorted in ascending order.
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return NULL;
element_t *node, *safe;
bool remove = false;
list_for_each_entry_safe (node, safe, head, list) {
if (&safe->list != head && !strcmp(node->value, safe->value)) {
remove = true;
list_del(&node->list);
q_release_element(node);
continue;
}
if (remove) {
remove = false;
list_del(&node->list);
q_release_element(node);
}
}
return true;
}
```
`safe` is next of `node` , so `&safe->list == head` means node is last node in list
[`strcmp(char *str1, char *str2)`](https://www.programiz.com/c-programming/library-function/string.h/strcmp) return `0` means `str1` is equal to `str2`, and also means the node need to be deleted in this case.
#### Step 1
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="cat|{<left>prev|<right>next}", style="bold"];
e3 [label="cat|{<left>prev|<right>next}", style="bold"];
e4 [label="bear|{<left>prev|<right>next}", style="bold"];
e5 [label="zebra|{<left>prev|<right>next}", style="bold"];
e6 [label="zebra|{<left>prev|<right>next}", style="bold"];
nodeptr [shape=plaintext;label="node"];
safeptr [shape=plaintext;label="safe"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
nodeptr -> e2 [color=red];
safeptr -> e3 [color=red];
}
```
`node` will be deleted
#### Step 2
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e3 [label="cat|{<left>prev|<right>next}", style="bold"];
e4 [label="bear|{<left>prev|<right>next}", style="bold"];
e5 [label="zebra|{<left>prev|<right>next}", style="bold"];
e6 [label="zebra|{<left>prev|<right>next}", style="bold"];
nodeptr [shape=plaintext;label="node"];
safeptr [shape=plaintext;label="safe"];
e1:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
nodeptr -> e3 [color=red];
safeptr -> e4 [color=red];
}
```
`remove == true` => `node` will be deleted
#### Step 3
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e4 [label="bear|{<left>prev|<right>next}", style="bold"];
e5 [label="zebra|{<left>prev|<right>next}", style="bold"];
e6 [label="zebra|{<left>prev|<right>next}", style="bold"];
nodeptr [shape=plaintext;label="node"];
safeptr [shape=plaintext;label="safe"];
e1:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
nodeptr -> e4 [color=red];
safeptr -> e5 [color=red];
}
```
#### Step 4
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e4 [label="bear|{<left>prev|<right>next}", style="bold"];
e5 [label="zebra|{<left>prev|<right>next}", style="bold"];
e6 [label="zebra|{<left>prev|<right>next}", style="bold"];
nodeptr [shape=plaintext;label="node"];
safeptr [shape=plaintext;label="safe"];
e1:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
nodeptr -> e5 [color=red];
safeptr -> e6 [color=red];
}
```
`node` will be deleted
#### Step 5
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e4 [label="bear|{<left>prev|<right>next}", style="bold"];
e6 [label="zebra|{<left>prev|<right>next}", style="bold"];
nodeptr [shape=plaintext;label="node"];
safeptr [shape=plaintext;label="safe"];
e1:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
nodeptr -> e6 [color=red];
safeptr -> e1 [color=red];
}
```
`remove == true` => `node` will be deleted
#### Result
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e4 [label="bear|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
### q_swap
* Attempt to swap every two adjacent nodes.
```c=
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *cur = head->next;
while (cur != head && cur->next != head) {
struct list_head *next = cur->next;
list_move(cur, next);
cur = cur->next;
}
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
```
### q_reverse
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *cur = head->prev->prev, *last = head->prev;
while (cur != head) {
list_move_tail(cur, head);
cur = last->prev;
}
}
```
#### Step 1
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
curptr [shape=plaintext;label="cur"];
lastptr [shape=plaintext;label="last"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
curptr -> e5 [color=red];
lastptr -> e6 [color=red];
}
```
#### Step 2
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
curptr [shape=plaintext;label="cur"];
lastptr [shape=plaintext;label="last"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
curptr -> e4 [color=red];
lastptr -> e6 [color=red];
}
```
#### Step 3
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
curptr [shape=plaintext;label="cur"];
lastptr [shape=plaintext;label="last"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
curptr -> e3 [color=red];
lastptr -> e6 [color=red];
}
```
#### Step 4
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
curptr [shape=plaintext;label="cur"];
lastptr [shape=plaintext;label="last"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
curptr -> e2 [color=red];
lastptr -> e6 [color=red];
}
```
#### Result
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
curptr [shape=plaintext;label="cur"];
lastptr [shape=plaintext;label="last"];
e1:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
curptr -> e1 [color=red];
lastptr -> e6 [color=red];
}
```
### q_sort
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one element, do nothing.
```c
struct list_head *merge_two_list(struct list_head *L1,
struct list_head *L2,
struct list_head *head)
{
struct list_head *tmp, *L1_last = L1->prev, *L2_last = L2->prev;
L1->prev->next = NULL;
L2->prev->next = NULL;
INIT_LIST_HEAD(head);
while (L1 && L2) {
if (strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) > 0) {
tmp = L2;
L2 = L2->next;
list_add_tail(tmp, head);
} else {
tmp = L1;
L1 = L1->next;
list_add_tail(tmp, head);
}
}
struct list_head *result = head->next;
list_del_init(head);
if (!L1) {
L2->prev = L2_last;
L2_last->next = L2;
list_add_tail(head, L2);
} else {
L1->prev = L1_last;
L1_last->next = L1;
list_add_tail(head, L1);
}
for (struct list_head *node = head->next; !list_empty(head);
node = head->next) {
list_move_tail(node, result);
}
return result;
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int size = q_size(head);
struct list_head *stack[size], *tmp = head->next;
for (int i = 0; tmp != head; tmp = head->next) {
list_del_init(tmp);
stack[i++] = tmp;
}
while (size > 1) {
for (int i = 0, j = size - 1; i < j; i++, j--) {
stack[i] = merge_two_list(stack[i], stack[j], head);
}
size = (size + 1) / 2;
}
list_add_tail(head, stack[0]);
}
```
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
```graphviz
digraph stack{
style=filled;
color="#a6cee3";
node[shape=record];
rankdir = LR;
subgraph cluster_level5{
label ="stack[0]";
e6 [label="5|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level4{
label ="stack[1]";
e5 [label="4|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level3{
label ="stack[2]";
e4 [label="3|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level2{
label ="stack[3]";
e3 [label="2|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level1{
label ="stack[4]";
e2 [label="1|{<left>prev|<right>next}", style="bold"];
}
e2:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
```graphviz
digraph stack{
style=filled;
color="#a6cee3";
node[shape=record];
rankdir = LR;
subgraph cluster_level5{
label ="stack[0]";
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level4{
label ="stack[1]";
e5 [label="4|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level3{
label ="stack[2]";
e4 [label="3|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level2{
label ="stack[3]";
e3 [label="2|{<left>prev|<right>next}", style="bold"];
}
e2:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
```graphviz
digraph stack{
style=filled;
color="#a6cee3";
node[shape=record];
rankdir = LR;
subgraph cluster_level5{
label ="stack[0]";
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level4{
label ="stack[1]";
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level3{
label ="stack[2]";
e4 [label="3|{<left>prev|<right>next}", style="bold"];
}
e2:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
```graphviz
digraph stack{
style=filled;
color="#a6cee3";
node[shape=record];
rankdir = LR;
subgraph cluster_level5{
label ="stack[0]";
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
}
subgraph cluster_level4{
label ="stack[1]";
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
}
e2:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
```graphviz
digraph stack{
style=filled;
color="#a6cee3";
node[shape=record];
rankdir = LR;
subgraph cluster_level5{
label ="stack[0]";
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
}
e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```
```graphviz
digraph ele_list{
rankdir=LR;
node[shape=record];
e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey];
e2 [label="1|{<left>prev|<right>next}", style="bold"];
e3 [label="2|{<left>prev|<right>next}", style="bold"];
e4 [label="3|{<left>prev|<right>next}", style="bold"];
e5 [label="4|{<left>prev|<right>next}", style="bold"];
e6 [label="5|{<left>prev|<right>next}", style="bold"];
e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e5:right:e -> e6:left:w[arrowhead=normal, arrowtail=normal, dir=both];
e6:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both];
}
```