#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct nodetype{ // 노드하나의 형식을 정의 해줍니다.
int data;
struct nodetype *pre_node; // 자신 이전을 가르키는 노드 입니다.
struct nodetype *next_node; // 자신 다음을 가르키는 노드 입니다.
}node;
typedef struct listtype{
int count; // 저장된 자료 개수 입니다.
node headnode; // 더미노드(해더노드)입니다.
}list;
list *makelist(){ // 리스트를 만드는 함수입니다.
list *returnlist; // 생성할 리스트 입니다. 반환 값
returnlist = (list *)malloc(sizeof(list));
if ( returnlist != NULL ){ // 리스트를 동적할당 한후 잘 되었는지 검사합니다.
memset(returnlist,0,sizeof(list)); // 리스트의 모든 변수를 0으로 초기화합니다.
returnlist -> headnode.next_node = &returnlist -> headnode;
returnlist -> headnode.pre_node = &returnlist -> headnode;
// 초기화시 이전과 다음을 자기 자신을 가르키게 합니다. 순환식을 이루 겠죠!!
}else{
printf("Error\n");
return 0;
}
return returnlist;
}
void Add(list *Plist, int p, node d){ // 자료를 추가하는 함수 입니다.
if ( p < 0 || p > Plist -> count ){ // 위치의 타당성을 검사합니다.
printf("Error!! value of Position\n");
return;
}else{
int i;
node *temp = &Plist -> headnode; // 임시노드입니다.
node *newnode = (node *)malloc(sizeof(node)); // 새로 추가시킬 노드입니다.
*newnode = d;
if ( newnode != NULL ){
for ( i = 0 ; i < p ; i++ ){ // 임시 노드를 이용해 원하는 위치로 이동합니다.
temp = temp -> next_node;
}
newnode -> pre_node = temp; // ①
newnode -> next_node = temp -> next_node; // ②
temp -> next_node = newnode; // ③
newnode -> next_node -> pre_node = newnode; // ④
//위치에 자료를 추가합니다. 자세한 과정은 아래 도식 참조~
Plist -> count++; // 저장된 자료 개수를 한단계 높여 줍니다.
return ;
}else{
printf("Error!!\n");
}
}
}
void Del(list *Plist, int p){ // 자료를 삭제하는 함수입니다.
node *free_node; // 자료를 삭제후 메모리를 반환해주는 변수입니다.
if ( p < 0 || p > Plist -> count ){ // 위치의 타당성을 검사합니다.
printf("Error!! value of Position\n");
return;
}else{
int i;
node *temp = &Plist -> headnode;
for( i = 0 ; i < p ; i++ ){
temp = temp -> next_node; // 임시노드를 이용하여 원하는 위치로 이동합니다.
}
free_node = temp -> next_node; // 삭제할 노드를 free_node에 저장합니다.
temp -> next_node -> next_node -> pre_node = temp; // ①
temp -> next_node = temp -> next_node -> next_node; // ②
//위치의 자료를 삭제합니다. 자세한 과정은 아래 도식 참조~
if ( free_node != NULL ){
free(free_node);
}
Plist -> count--;
return;
}
}
//이하의 자료 검색은 이전에 했던 리스트와 같으므로 설명 생략~
void Seek(list *Plist, int p){
if ( p < 0 || p > Plist -> count ){
printf("Error! value of Position\n");
}else{
int i;
node *temp = &Plist -> headnode;
for ( i = 0 ; i <= p ; i++ ){
temp = temp -> next_node;
}
printf("%d번째 자료 : %d\n",p,temp->data);
return ;
}
}
//자료 출력함수도 똑같으나... 이중 연결이 잘되어있는지 확인하기위해
//역순으로 출력하는 것도 첨가하였다.
void Display(list *Plist){
node *temp = &Plist -> headnode;
int i;
for ( i = 0 ; i < Plist -> count ; i++ ){
temp = temp -> next_node;
printf("%d번째 자료 값 : %d\n",i, temp -> data);
}
temp = &Plist -> headnode;
printf("\n\n역순인쇄\n\n\n");
for ( i = Plist -> count - 1 ; i >= 0 ; i-- ){
temp = temp -> pre_node;
printf("%d번째 자료 값 : %d\n",i, temp -> data);
}
}
//메인은 역시 자기 맘대로 꾸미기~!
int main(){
list *DL;
DL = makelist();
while(1){
int select;
int position;
node datanode;
printf("\n\n\n현재 %d개의 자료 저장중\n",DL -> count);
printf("기능을 선택해주십시요.\n");
printf("1.자료저장\t2.자료삭제\t3.자료검색\t4.전체자료보기\t5.종료\n");
scanf("%d",&select);
switch(select){
case 1:
printf("저장 위치 : ");
scanf("%d",&position);
printf("저장 자료 : ");
scanf("%d",&datanode.data);
Add(DL,position,datanode);
break;
case 2:
printf("삭제할 자료 위치 : ");
scanf("%d",&position);
Del(DL,position);
break;
case 3:
printf("찾을 자료 위치 : ");
scanf("%d",&position);
Seek(DL,position);
break;
case 4:
Display(DL);
break;
case 5:
if( DL != NULL ){
free(DL); // 마지막 종료시에는 자료를 메모리에서도 지워줍니다.
}
return ;
default:
printf("You don't press colect number");
}
}
}
------------------------------------------------------------------------------------------------
위의 자료 구조를 일단 보자...
음음... 먼가 보통의 책들과는 다른 모습이다. 그냥 원래 있던 형식을 유지하고 싶어서(귀찮은것뿐이잖아!!)
그냥 했다-_-;
그럼 이젠 추가 및 삭제 과정을 보자
ⓐ 추가
그림이 먼가 어지럽지만... 말로 한다면
일단 1번위치에 새로운 자료를 추가하는 것이고,,,
새로운 노드의 이전과 다음을 연결한후(①,②)
원래 있던 노드의 연결을 새로 해준다(③,④)
다음은 삭제에 대해서 알아보자
ⓑ 삭제
흠... 내 그림 표현실력에 의문이 가해지고있다....
므튼.. 이것도 말로하자면
1번노드를 삭제하는 과정이다.
1번노드에 관계없이 1번노드의 이전노드인 0번 노드와 다음노드인 2번노드와의 연결을 만들고(①,②),
2번노드를 메모리에서 삭제해주면된다.
-----------------------------------------------------------------------------------------------
이중 연결 리스트(더블 링크리스트)에 대해서 알아봤다.
먼가 이해가 될지 안될지 모르겠지만, 끝까지 읽어줘서 고맙다...
이중 연결 리스트는 여러 곳에서 사용 할수 있다. 예전에 프로잭트할때 한번 사용했는데...
지금 생각해보면 굳이 이중을 안써도 되는 것이였다...;; 므튼...