Latest revision as of 04:26, 11 July 2012

Lecture Fri 23Mar Peachanok Lertkajornkitti ECE 264

Lecture 19, ECE264, Spring 2012, Prof. Lu

Linked List

-resizable -do not allow random access -insertion at any point

Example of linked list:

typedef struct int_node_t{ int value; struct int_node_t *next;

} IntNode;

IntNode *IntNode_create(int value) { IntNode *node = malloc(sizeof(IntNode)); node->value = value; node->next = NULL; return node; }

===================

Kevin Tan(0023987592), section#2 notes 03/27

Node *Node_construct(int v, Node *Next) {

 Node *n;

 n = malloc(sizeof(Node));
 n->next = Next;
 n->value = v;

 return n;

}

Node *List_insert(Node *h, int v) {

 Node *n = Node_construct(v,NULL);
 n->next = h;
 
 return n;

}

void List_print(Node *h) {

 Node *p = h;

 while (p != NULL)
   {
     printf("%d\n", p->value);
     p = p->next;
   }

}

void List_destroy(Node *h) {

 Node *p;
 Node *q;
 p=h;
 while (p != NULL)
   {
     q = p->next;
     free(p);
     p = q;
   }

}

int main(int argc, int argv[]) {

 Node *head = NULL;
 head = List_insert(head,6);
 head = List_insert(head,29);
 head = List_insert(head,-74);
 List_print(head);
 List_destroy(head);

} void IntNode_destroy(IntNode *node) { free(node); }

int IntNodeL_elementAt(IntNode *head, int index) { if (head == NULL) return NULL; while(index-- > 0){ head = head->next; } return head; } } IntNode *IntNodeL_insert(IntNode *head, int value) { IntNode *node = IntNode_create(value); node->next = head; return node; }

void IntNodeL_print(IntNode *head) { while(head != NUll){ printf("%d\n",head->value); head=head->next; } }

void IntNodeL_destroy(IntNode *head) { while(head != NULL) { IntNode *tmp = head; head = head->next; IntNode_destroy(tmp); } } IntNode *IntNodeL_insertBack(IntNode *head, int value) { IntNode *node = IntNode_create(value, NULL); if(head == NULL) return node; IntNode *pos = head; while(pos->next != NULL){ pos = pos->next; } pos->next = node; return head; } int main(int argc, char *argv[]) { int i; IntNode *head = NULL; for(i=0;i<100;i++) { head = IntNodeL_insert(head, i); }

IntNodeL_print(head); IntNodeL_destroy(head); return EXIT_SUCCESS; }

IntNode *IntNodeL_reverse(IntNode *head) { if(head == NULL) return NULL; IntNode *new_head = NULL; while (head != NULL) { IntNode *tmp = head; head = head->next; tmp->next = new_head; new_head = tmp; }

return new_head;

} ////////******

Lecture notes 19_Mar 22_Kailu Song

1. Three ways to allocate memory: a. static -> know the size when writing the program e.g. int arr[00]; int arr[200]; b. know the size somewhere during execution. e.g. int length; scanf(“%d”, &length); arr = malloc(sizeof(int)*length); c. grow and shrink based on run-time needs(dynamic structure) e.g. link list

      binary tree

2. Example Code Typeof struct dstructure { /*data*/ int value; Vector vec; Person *P; /*LINK*/ struct dsturcture *next;(linked list) struct dsturcture *left; struct dsturcture *right;(binary tree) }Node; 3. How to use linked list Node *n; n = malloc(sizeof(Node)); n->value = 27; n->next = NULL; typeof struct listnode(define linked list) { int value; struct listnode * next; }Node; Node *n = NULL; n = malloc(sizeof(Node)); n->value = 264; n->next = NULL; Node *n2; n2= malloc(sizeof(Node)); n2->value = 264; n2->next = NULL; n->next=n2;

Node*n3; n3 = n;(modify stack for n3) printf(“%d”,n3->value);(=264) n3 = n3->next;(change stack memory for n3) printf(“%d”,n3->value);(=2012) Node * Node_construct (int V) { n = malloc(sizeof(Node)); n->value = v; n->next = NULL; return n; } Node *List_insert(Node *t, int V) { Node *n; n = Node_construct(v); n->next = t; return n; } Node *head = NULL; head = List_insert(head,264); head=List_insert(head,2012);

ECE264 LEC19 Shiyu Wang Mar 25

There are three ways to allocate memory 1. Static(know the size when writing the program) eg. int arr[100]; vector v[200];

2. know the size somewhere during execution eg. int length; scanf("%d",&length)

int *arr; arr=malloc(sizeof(int)*length);

3.grow and shrink based on run-time needs(dynamic structures) eg. linked list, binary tree

EXAMPLE

typedef struct destructure {

 /*data*/
 int value;
 vector vec;
 person *p;
 ...
 /*link*/
 struct destructire *next;(linked list)
 struct destructure *left;(binary tree)
 struct destructure *right;(binary tree)

}Node;

How to use linklist Node * n; n=malloc(size of(Node)) n-> value=27 n->next = NULL;

Expressive1 type def struct list node {

 int value;
 struct list node* next;

}Node;

Expressive2 Node*n=NULL; n=malloc(size of (Node)); n->value = 264; n -> next=NULL; Node *n2; n2=malloc(size of (Node)); n2->value = 2012; n2->next = n2;

Expressive 3 Node *n3 n3=n; printf("%d",n3->value); n3=n3->next; printf("%d",n3->value);

Structure Node *Node_construct(int U) {

 Node *n;
 n=malloc(sizeof(Node));
 n->value = v;
 n->next = NULL;
 return n;

}

Node *List_inserct(Node *t,int v) {

 Node *n = node_construct (v);
 n->next = t;
 return n;

}

Node *head = NULL; head=list_inserct(head,264); head=list_inserct(head,2012);

=======================

Hanye Xu 0024242156 Lec19

Node *Node_construct(int v, Node *Next) {

Node *n;
n = malloc(sizeof(Node));
n->next = Next;
n->value = v;
return n;

}

Node *List_insert(Node *h, int v) {

Node *n = Node_construct(v,NULL);
n->next = h;

return n;

}

void List_print(Node *h) {

Node *p = h;
while (p != NULL)
  {
    printf("%d\n", p->value);
    p = p->next;
  }

}

void List_destroy(Node *h) {

Node *p;
Node *q;
p=h;
while (p != NULL)
  {
    q = p->next;
    free(p);
    p = q;
  }

}

how to use:

Node *head = NULL;
head = List_insert(head,6);
head = List_insert(head,29);
head = List_insert(head,-74);
List_print(head);
List_destroy(head);

} void IntNode_destroy(IntNode *node) { free(node); }

==================

Rohan Khante

=====================

Linked Lists are generally used to to represent a sequence whose length is not known at the start. They can be used to store as many elements as you want. This is the key difference between an array and a Linked List. Linked Lists can be loosely classified as an array of structures with an additional pointer to the next structure.

typedef struct listnode { struct listnode * next;

int value;

} Node; This is a typedef for a node. A node here contains an integer and a POINTER to the next node. Node = integer plus a pointer to a next node. The keyword typedef has been used here to give a name to the structure that is being created. The name Node has been chosen here.

Static Node * Node_construct(int v) { Node * n = malloc(sizeof(Node));

n -> value = v;

n -> next = 0;

return n; }

Here we are interested in creating a node with the value ‘v’. For this Node_construct is being made since it will automatically due to memory allocation for us and store the value of the integer inside it. Since we are interested in creating a node the return type of the function has been specified as Node. Malloc is done to allocate memory. It will malloc memory equal to the size of the node(For size refer to the typedef above) n->value refers to the value inside the Node. N-next is a pointer to the next Node. It has been assigned to zero here.(More on this below)

Node * List_insert(Node * head, int v) { printf("insert %d\n", v);

Node * p = Node_construct(v);

p -> next = head;

return p; /* insert at the beginning */ }

This is used to generate a list. In this a pointer to the head(START of the list) is passed as well as the value to be inserted into a node. Node is constructed using the Node_construct function. P->next = head means that the pointer inside the Node will now point towards the head node. Since a new node is being created which points towards the head of a list this implies that the new node is inserted at BEGINNING of the list. Example calling this function repeatedly on values 2,3,4,5 in order will give you a list with 5,4,3,2.(order REVERSED)

Node * List_search(Node * head, int v) { Node * p = head;

while (p != NULL)

{

if ((p -> value) == v)

{

return p;

}

p = p -> next;

}

return p;

}

This function searches for a node having a value v and return the pointer to it. A node is created inside the function and is initialized to head. P!=NULL checks wether the head is empty or not(whether the list is empty or not). If it finds the value at a certain node it return that node. P = p->next is ANALOGOUS to i++ where i is a loop variable used generally in while loops. The node is finally returned.

Node * List_delete(Node * head, int v) { printf("delete %d\n", v);

Node * p = head;

if (p == NULL) /* empty list, do nothing */

{

return p;

}

/* delete the first node (i.e. head node)? */

if ((p -> value) == v)

{

p = p -> next;

free (head);

return p;

}

/* not deleting the first node */

Node * q = p -> next;

while ((q != NULL) && ((q -> value) != v)) {

/* must check whether q is NULL

before checking q -> value */

p = p -> next;

q = q -> next;

}

if (q != NULL)

{

/* find a node whose value is v */

p -> next = q -> next;

free (q);

}

return head;

}

This function deleted a node whose value is equal to the value being inputed into the function. It first ensures that the list is not empty. The function depends on whether the first element is being deleted or not. IF the first element is deleted the function changes the head so that it becomes the node that it was previously pointing to. Then the original head is deleted .

void List_destruct(Node * head) {

while (head != NULL)

{

Node * p = head -> next;

free (head);

head = p;

} } Here head is being incremented and freed. First a node is being created and gets pointed to the next location stored in head. The head is then freed. The now NEW starting location is labeled as head.

void List_print(Node * head) { printf("\nPrint the whole list:\n");

while (head != NULL)

{

printf("%d ", head -> value);

head = head -> next; }

printf("\n\n"); }

This function prints the entire list in order. The function should be self-explanatory at this stage. Head= head->next changes the head to the next node.

Back to ECE264, Spring 2012, Prof. Lu