연결 리스트 (Linked List)

개념
자료들을 임의의 기억공간에 저장시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조 각 노드는 다음 노드를 가리키는 링크(Link, Pointer) 정보를 가지고 마지막 노드는 포인터 정보를 Null 값을 가짐.

I. 연결 리스트 (Linked List)의 개요

가.  연결 리스트의 정의

- 자료들을 임의의 기억공간에 저장시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조

 

- 각 노드는 다음 노드를 가리키는 링크(Link, Pointer) 정보를 가지고 마지막 노드는 포인터 정보를 Null 값을 가짐.

 

 

나. 연결리스트의 장∙단점

(1)   장점

- 자료의 삽입 및 삭제가 용이

- 기억장소의 이용 효율이 좋음.

 

(2)   단점

- Access Time이 느림

- 포인터를 위한 추가 공간이 필요

 

Ⅱ. 연결 리스트 (Linked List)의 구현 방법

가. 연결 리스트의 삽입 구현

“cat”과 “sat”사이에 “mat”을 삽입한다면~

(1) 기억장소로부터 노드를 얻는다. (주소값: paddr)

  (2) 노드에 “mat” 데이터를 저장한다.

(3) paddr 노드의 링크값에 “cat”노드의 링크값을 저장한다.

(4) “cat” 노드의 링크값에 paddr을 저장한다.

void insert(list_ptr *ptr,list_ptr node) {

 list_ptr temp;

 temp=(list_ptr)malloc(sizeof(list_node));

 if(!temp ) {

  fprintf(stderr,”The momory is full\n”);

  exit(1);

 }

 temp->data=”mat”;

 if(*ptr) {

  temp->link = node->link;

  node->link = temp;

 }

 else {

  temp->link = NULL; *ptr = temp;

 }

}

 

나. 연결 리스트의 삭제 구현

- ptr: 리스트 첫 노드를 가리키는 포인터 변수

- node: 삭제될 노드를 가리키는 변수

- trail: 삭제될 노드의 바로 앞 노드를 가리키는 변수

 

* 삭제될 노드가 첫 노드일 경우와 그렇지 않은 경우로 나눔

  (1) 삭제될 노드가 리스트의 첫 노드일 때 – 리스트 시작인 ptr 값이 바뀐다.

      

(2) 그 외의 경우 리스트의 시작인 ptr 값이 안 바뀐다.

    

void delete(list_ptr *ptr, list_ptr trail, list_ptr node){

 if(trail) /* 노드가 여러 개 있는 경우 */

  trail->link = node->link;

 else /* 노드가 한 개 밖에 없는 경우 */

  *ptr = (*ptr)->link;

 free(node);

}

Ⅲ. 연결 리스트 (Linked List)의 종류

구분

내용

단순 연결 리스트

(Single Linked List)

이중 연결 리스트

(Double Linked List)

환형 연결 리스트

(Circular Linked List)

 

 

댓글