a linked-list is a data structure that consists of a sequence of data records, and each record includes a field that contains a reference (link) to the next record in the sequence. the principal benefit of using a linked-list over an array is that the order of the linked items can differ from the order in which the data items are stored in memory or on disk. therefore, linked lists allow the insertion & removal of nodes at any point in the list
#C CODE SNIPPET
struct node
{
int x;
struct node * next;
};
typedef struct node pnode;
void main()
{
pnode * curr, * head;
int i;
head = NULL;
for(i=1;i<=10;i++) ❶
{
curr = (pnode *)malloc(sizeof(pnode));
curr->x = i;
curr->next = head;
head = curr;
}
curr = head;
while(curr) ❷
{
printf("%d\n", curr->x);
curr = curr->next ;
}
}
* the first loop at (1) creates 10 nodes & fills them with data
* the second loop at (2) iterates over all the records & prints their contents
#ASSEMBLY CODE SNIPPET
0040106A mov [ebp+var_8], 0
00401071 mov [ebp+var_C], 1
00401078
00401078 loc_401078:
00401078 cmp [ebp+var_C], 0Ah
0040107C jg short loc_4010AB
0040107E mov [esp+18h+var_18], 8
00401085 call malloc
0040108A mov [ebp+var_4], eax
0040108D mov edx, [ebp+var_4]
00401090 mov eax, [ebp+var_C]
00401093 mov [edx], eax ❶
00401095 mov edx, [ebp+var_4]
00401098 mov eax, [ebp+var_8]
0040109B mov [edx+4], eax ❷
0040109E mov eax, [ebp+var_4]
004010A1 mov [ebp+var_8], eax
004010A4 lea eax, [ebp+var_C]
004010A7 inc dword ptr [eax]
004010A9 jmp short loc_401078
004010AB loc_4010AB:
004010AB mov eax, [ebp+var_8]
004010AE mov [ebp+var_4], eax
004010B1
004010B1 loc_4010B1:
004010B1 cmp [ebp+var_4], 0 ❸
004010B5 jz short locret_4010D7
004010B7 mov eax, [ebp+var_4]
004010BA mov eax, [eax]
004010BC mov [esp+18h+var_14], eax
004010C0 mov [esp+18h+var_18], offset aD ; "%d\n"
004010C7 call printf
004010CC mov eax, [ebp+var_4]
004010CF mov eax, [eax+4]
004010D2 mov [ebp+var_4], eax ❹
004010D5 jmp short loc_4010B1 ❺
* the best way to understand the disassembly is to identify the two code constructs w/i the main method
- to recognize a linked-list, the analyst must first recognize that some object contains a pointer that points to another object of the same type
- the recursive nature of the objects is what makes it linked, & this is what is needed to recognize it in assembly
