[데이터 구조] 9차시 연결 데이터 표현 | 단순 연결 리스트

1. 단순 연결 리스트의 정의 및 특징

• 정의: 하나의 링크 필드를 가진 노드들이, 모두 자기 후속 노드와 연결되어 있는 노드 열(list)
• 특징: 마지막 노드의 링크 필드는 리스트의 끝을 표시하는 null 값을 가짐
• 별칭: 선형 연결 리스트(linear linked list), 단순 연결 선형 리스트(singly linked linear list), 연결 리스트(linked list), 체인(chain)

 

 

2. 삽입과 삭제 연산 개념

1) 원소 삽입 연산

(1) Node 삽입 연산이란?

• list에는 포인터 변수, ptr이 가리키는 list로서, 기존에 10과 20이 있음.
• list의 추적을 위한 포인터 변수, node_tracer를 선언하고 이를 ptr과 같은 노드를 지칭하게 함
• 50을 가진 새로운 노드를 malloc() 함수로 생성한 후, 노드를 지칭하기 위한 임시 포인터인 temp가 이 노드를 가리키게 함
• node_tracer가 가리키는 노드의 다음 위치에, temp가 가리키는 새로운 node 50을 삽입하는 연산임

 

struct node {
    int data;
    struct node *link;
}

struct node *ptr, *node_tracter, *temp;
ptr = (struct node *)malloc(sizeof(struct node)); /*type casting*/
node_tracter = ptr;
prt -> data = 10;
ptr -> link -> data = 20;
temp = (struct node*)malloc(sizeof(struct node)); /*type casting*/
temp -> data = 50;
temp -> link = node_tracter -> link;
node_tracer -> link = temp;
node_tracter = ptr;

while(node_tracer -> link != null){
    printf("current node is %d\n", node_tracer -> data);
    node_tracer = node_tracer -> link;
}

while(node_tracer -> data != 20){
    for(i=1; i<=100; i++){
    	node_tracer = node_tracer -> link;
        printf("data is =%d\n", node_tracer -> data);
    }
}

 

 

 

 

(2) 예시

• 사용하지 않은 새로운 node를 할당받는다(변수 paddr이 가리키고 있다)
• 이 node의 data field에 mat를 지정한다 (여기부터 순서 주의)
• 이 node의 link field가 cat를 포함하는 node의 link field값을 갖도록 한다.
• cat를 포함하는 node의 link field에 paddr을 지정한다.

 

 

 

 

 

 

2) 원소 삭제 연산

 

 

 

 

3. C언어 구현