링크드리스트의 모든 것 linked list

작성중....................

#include <stdio.h>









/////////////////////////////////single linked list

/* head를 기준으로 head에 계속 update하는 것. 
//stack 같은거 구현 시 용이 함 . 이 때는 count라는 변수를 두어서 pop시 에러처리 해줄 수 있음.
// head = head->next 
struct Node {
int data;
Node *next;
};

Node buf[10000];
int bufCnt;

Node *head;

Node *myAlloc(int data, Node *next)
{
buf[bufCnt] = { data, next };
return &buf[bufCnt++];
}

void myAlloc(int data)
{
head = myAlloc(data, head);
}

Node *search(int data)
{
for(Node *p = head; p != 0x0; p = p->next)
if (p->data == data)
return p;

return 0x0;
}
*/

/*
//head를 기준으로 head는 처음에 들어온 것을 가리키고 그 뒤에다가 계속 넣는 방식
//last가 필요함.
//queue같은 경우 구현 용이. count 변수 두어서 에러처리 deque시 // head에서 계속 빼가면 돼. head = head->next 식으로 update 

struct Node {
int data;
Node *next;
};

Node buf[10000];
int bufCnt;

Node *head;
Node *last;

Node *myAlloc(int data, Node *next) 
{
buf[bufCnt] = { data, next };
return &buf[bufCnt++];
}

void addNode(int data)
{
if (head == 0x0)
head = last = myAlloc(data, 0x0);
else 
last = last->next = myAlloc(data, 0x0); // myAlloc(data, last->next)
}

Node* search(int data)
{
for (Node* p = head; p != 0x0; p = p->next) {
if (p->data == data)
return p;
}
return 0x0;
}
*/


//single linked list에서의 dummy 사용은?

//head에 넣는 방법 시 dummy
/*
struct Node {
int data;
Node *next;
};

Node buf[10000];
int bufCnt;

Node *head;
Node *myAlloc(int data, Node *next)
{
buf[bufCnt] = { data, next };
return &buf[bufCnt++];
}

void init()
{
bufCnt = 0;
head->next = myAlloc(-1, 0x0);
}

void addNode(int data)
{
head->next= myAlloc(data, head->next);
}
TODO : 장점은? 
*/ 





//////////////////////////////////////////////////////double linked list

/* 
//더블링크드리스트 head기준 head에다가 계속 update하는 방법. last필요 없음

struct Node {
int data;
Node *next;
Node *before;
};

Node buf[100000];
int bufCnt;

Node *head;
Node *myAlloc(int data, Node *next, Node *before)
{
buf[bufCnt] = { data, next, before };
return &buf[bufCnt++];
}

void addNode(int data)
{
head = myAlloc(data, head, 0x0);

if (head->next != 0) 
head->next->before = head;
}
*/


/*
//더블링크드리스트 last기준 계속 update하는 방법. 
struct Node {
int data;
Node *next;
Node *before;
};

Node buf[10000];
int bufCnt;

Node *head;
Node *last;

Node *myAlloc(int data, Node *next, Node *before)
{
buf[bufCnt] = { data, next, before };
return &buf[bufCnt++];
}

void addNode(int data)
{
if (head == 0x0)
head = last = myAlloc(data, 0x0, 0x0);
else
last = last->next = myAlloc(data, last, last->next); // myAlloc(data, last, 0x0);
}
*/

// dobule linked list는 어떤 방법을 하더라도, 
// 기존의 single linked list는 head에 update하는 방식(last를 안 쓰고)을 쓰면 
// addNode시에 조건에 대한 분기가 이뤄지지 않는 방법이 있었는데
// double linked list는 어떤 방법을 쓰더라도 분기가 일어나야 해.. 이를 막기 위해 dummy node를 추가하는 방법이 나타남


/*
struct Node {
int data;
Node *next;
Node *before;
};

Node buf[10000];
int bufCnt;

Node *head;
Node *last;


void init()
{
bufCnt = 0;
head = myAlloc(-1, 0x0, 0x0);
last = head->next = myAlloc(-2, 0x0, head);
// data는 그때그때 따라 사용하지 않는 값으로 적절하게. 
//이 경우는 data가 양수 이상으로 들어온다. 가정 시 음수 값을 assign하면 dummy node인지 판별하는 지표가 됨.
// head -> |-1 <-> -2| <- last
}
Node *myAlloc(int data, Node *next, Node *before)
{
buf[bufCnt] = { data, next, before };
return &buf[bufCnt++];
}

void addNode(int data)
{
head->next = myAlloc(data, head->next, head);
head->next->next->before = head->next;
}*/

/*
//last 를 씀에도 불구하고 head에 addNode를 update하는데 왜 last가 필요? --> init시 편하기 위해서..
//dummy node를 2개 쓰는 이유?  --> 그래야 중간에 삽입하는 그림이 되기 때문에 통일할 수 있다. 
//아래처럼 1개로 써도 되긴 됨. 근데 삭제 시 맨끝 node인지 중간 node인지에 따라 구분해야해.
void addNode(int data)
{
head->next = myAlloc(data, head->next, 0x0);
if (head->next != 0x0)
head->next->next->before = head->next;
}
*/