컴퓨터과학 자료구조 연결리스트

리스트의 개념

- 일정한 순서의 나열

 - 논리적인 순서의 나열

 - 리스트에 나타나는 원소들 간의 '의미적인 순서'

리스트의 의미

 - 원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들 간의 논리적인 순서만 유지함

포인터를 이용한 리스트의 구현 : 원소값을 저장하는 공간과 다음 원소의 위치정보를 저장하는 방법을

함께 구현

노드 : 리스트의 원소(값) + 다음원소를 가리키는 정보

단순 연결리스트 : 링크부분이 하나, 각각의 노드는 후행만 바라봄, 특정 후행은 쉽게 바라보지만 다른 것은

바라보기 어렵다. so, 특정 노드가 두 개의 링크필드를 가지는 이중연결 리스트를 만든다.

이중연결리스트 : 특정 노드는 선행노드링크. 후행노드링크를 가진다.

양쪽방향으로 순회할 수 있도록 링크가 두 개 필요하다. 메모리는 더 차지하지만 성능 up

원형연결리스트 : 연결리스트 가장 마지막 노드 링크 부분은 null인데 이 부분까지 활용할 수 있다.

단순연결리스트의 단점 : 특정 노드의 후행노드는 쉽게 찾을 수 있으나 선행노드를 찾으려면 

복잡한 방법이 필요하다.

.

연습문제

1. 다음 중 리스트에 대한 설명으로 틀린 것은 ? 

 - 메모리 공간에서 물리적 위치와 논리적 위치는 일치한다(X)

(2 ~ 3) 다음 프로그램은 2개의 노드로 구성된 연결리스트의 노드 생성과 연결에 관한 프로그램이다. 문제를 읽고 빈칸을 알맞은 답을 구하시오.

typedef struct ListNode { // 단순 연결 리스트의 노드 구조 정의

        int data[10];

        [가]   --> lstruct ListNode* link;

} listNode;

typedef struct { // 리스트의 헤드(first) 노드 구조 정의

        listNode* head;

} linkedList_h;

linkedList_h* createLinkedList_h(void) { // 연결리스트 생성

        linkedList_h* H;

        [나] --> H = (linkedList_h*(malloc(sizeof(linkedList_h));

        H → head = NULL;

        return H;

}

4. 원형 연결 리스트에 대한 설명으로 틀린 것은?

 - 단순 연결리스트에 비해 추가적인 메모리가 필요하다(X)

(5 ~ 6) 다음 프로그램은 2개의 노드로 구성된 연결리스트의 노드 생성과 연결에 관한 프로그램이다. 문제를 읽고 빈칸을 알맞은 답을 구하시오.

① void addNode(linkedList_h* H, int x) {

        listNode* NewNode;

②      listNode* LastNode;

③      NewNode = (가) --> (listNode*)malloc(sizeof(listNode));

④      NewNode → data = x;

⑤      NewNode → link = NULL;

⑥      if ( H → head == NULL) { // 현재 리스트가 공백이면

⑦         (나) --> H → head = NewNode;

⑧          return;

⑨      }

⑩      LastNode = H → head;

⑪      while(LastNode → link != NULL)

⑫        LastNode = LastNode → link;

⑬      LastNode → link = NewNode;

⑭  }