single linked list	double linked list
링크 개수	한 방향 링크	양방향 링크
지나온 부분을 탐색하고자 할 때,	다시 head에서부터 탐색해야 함	앞 링크를 통해 뒤로 탐색 가능
		탐색속도 빠름
		메모리 손해 (링크가 2개)

지나온 부분을 탐색하고자 한다 == 뒤로 탐색한다.

ADT

배열에선 삽입 시, 지정 크기를 넘어갈 때 malloc 을 통해 삽입한다.
linked list: 삽입/삭제 (... + 임의 위치 삽입, 뒤집기, 파라미터 없이,...)
모두다 기능인 ADT다... 구현은 몰겠고 어쨌든 기능이야

• single linked list에서의 struct node

Struck Node_{
	 int data;
	 Struct Node_* ptr;
}

• double linked list에서의 struct node

Struct Node_{
	int data;
	struct Node_* prev;
	Struct Node_* next;
}

이중 연결 리스트의 구조는 다음과 같다.
이전 노드를 가리키기 위해 추가 메모리가 필요하다. 따라서 링크가 두개!

이중연결리스트 삽입

• InsertAtHead(x)
• InsertAtTail(x)

이중연결리스트 출력

• Print()
• ReversePrint()

Struct Node_{
	int data;
	struct Node_* prev;
	Struct Node_* next;
}
typedef Struct Node_ Node;

Node head;

int main(){
	x입력받기
	insertAtHead(x);
}

void insertAtHead(int x){
	Node* tmp = (Node*)malloc(sizeOf(Node));
	tmp -> data = x;
	tmp -> prev = NULL;
	tmp -> next = NULL;
	.
	.
	.
}

여기서 void insertAtHead 내부에서 malloc으로 node pointer타입의 변수를 선언하고, data, prev, next를 할당해주는 부분은 반복된다.
따라서 GetNewNode라는 함수로 빼낸다.

Struct Node_{
	int data;
	struct Node_* prev;
	Struct Node_* next;
}
typedef Struct Node_ Node;

Node head;

int main(){
	x입력받기
	insertAtHead(x);
}

void GetNewNode(int x){
	Node* newNode = (Node*)malloc(sizeOf(Node));
	newNode -> data = x;
	newNode -> prev = NULL;
	newNode -> next = NULL;

	return newNode;	
}
void insertAtHead(int x){
	Node* tmp = GetNewNode(x);
	.
	.
	.
}

즉, 위와 같은 형태로 바뀐다.

Struct Node_{
	int data;
	struct Node_* prev;
	struct Node_* next;
}
typedef struct Node_ Node;

Node head;

int main(){
	int x;
	printf("input x: ");
	scanf("%d", &x);
	insertAtHead(x);
}

void GetNewNode(int x){
	Node* newNode = (Node*)malloc(sizeOf(Node));
	newNode -> data = x;
	newNode -> prev = NULL;
	newNode -> next = NULL;

	return newNode;	
}
void insertAtHead(int x){
	Node* tmp = GetNewNode(x);
	if(head == NULL){
		head = tmp;
		return;
	}
	head -> prev = tmp;
	tmp -> next = head;
	head = tmp;
}

int main(){
	insertAtHead(2);
}

void insertAtHead(int x){
	Node* tmp = GetNewNode(x);
	if(head == NULL){
		head = tmp;
		return;
	}
	head -> prev = tmp;
	tmp -> next = head;
	head = tmp;
}