첫 번째 노드를 저장하는 head 노드, 마지막 노드의 링크 필드는 NULL ~ 연결 리스트의 끝 표시
노드
typedef struct node{
char *data; //연결 리스트에 저장할 데이터 타입 지정
struct node * next; //다음 노드의 주소를 저장할 필드, 자기 참조형 구조체
}Node;
Node *head = NULL; //연결 리스트의 첫 번째 노드의 주소를 저장할 포인터
자기 참조형 구조체: 자신과 동일한 구조체에 대한 포인터를 멤버로 가진다.
struct node *next: struct node를 가리키고 있는 struct node 타입의 포인터 변수
//삭제하고자 하는 노드 p
//삭제하고자 하는 노드의 이전 노드 q
if(q==NULL){
head = p->next;
free(p);
}
이외의 경우
p 노드가 맨 마지막 노드이더라도 p→next는 NULL 이기 때문에 q→next = NULL;
else{
q->next = p->next;
free(p);
}
자료구조 13강
양방향 연결 리스트의 Node
typedef struct node{
char *data;
struct node *next;
struct node *prev;
}Node;
Node *head; //연결 리스트의 첫 번쨰 노드 주소 저장
Node *tail; //연결 리스트의 마지막 노드 주소 저장
양방향 연결 리스트에서의 삽입
앞 노드의 주소가 있어야 그 뒤에 삽입이 가능한단방향 리스트와 다르게
양방향 연결 리스트에서는prev와next를 통해어떤 노드의 앞에노드를 삽입할 수 있다.
[어떤 노드 앞에 새로운 노드 삽입하기] ‼️새로운 노드 → 앞 연결 → 뒤 연결‼️ (순서 유의) (0) 새로운 노드를 만들고 추가할 데이터를 저장한다. (1) 새로운 노드의 링크를 먼저 연결한다. (2) 새로운 노드의 앞 노드가 새로운 노드를 가리키도록 한다. (3) 새로운 노드의 뒷 노드가 새로운 노드를 가르키도록 한다.
//(0) 새로운 노드를 만들고 추가할 데이터 저장하기
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->data = "by";
//(1) 새로운 노드의 링크를 먼저 연결
new_node->next = p;
new_node->prev = p->prev;
//(2) 새로운 노드의 앞 노드가 새로운 노드를 가리키도록
p->prev->next = new_node;
//(3) 새로운 노드의 뒷 노드가 새로운 노드를 가리키도록
p->prev = new_node;
[case 별로 어떤 노드뒤에 새로운 노드 삽입하기] ‼️새로운 노드 → 뒤 연결 → 앞 연결‼️ (순서 유의)
//head가 NULL이면 empty list, empty list이기 때문에 pre도 NULL
if(pre==NULL && head==NULL){
head = new_node;
tail = new_node
}
맨 앞에 삽입하는 경우
//head != NULL일 떄 pre==NULL이면 제일 앞에 삽입해야 하는 경우
else if(pre==NULL){
new_node->next = head;
head->prev = new_node;
head = new_node; //첫 노드의 주소를 가지고 있는 head노드를 가장 마지막에
}
맨 마지막에 삽입하는 경우
//pre 뒤에 삽입해야하는데, pre가 마지막이면 마지막에 삽입해야 하는 경우
else if(pre==tail){
new_node->prev = tail;
tail->next = new_node;
tail = new_node; //마지막 노드의 주소를 가지고 있는 head노드를 가장 마지막에
}
양방향 연결 리스트에서는삭제하고자 하는 노드만있다면 그 노드를 삭제할 수 있다.[노드 삭제하기] ‼️앞 → 뒤‼️ (순서 유의) (1) 삭제할 노드의 앞 노드가 삭제할 노드의 뒷 노드를 가리키도록 한다. (2) 삭제할 노드의 뒷 노드가 삭제할 노드의 앞 노드를 가리키도록 한다.
[노드 삭제하기] ‼️앞 → 뒤‼️ (순서 유의)