2.2.2 연결 리스트 (Linked List)

2.2.2 연결리스트

- 개념 : 1) 동적으로 크기가 변할 수 있고, 삽입이나 삭제 시 데이터 이동할 필요가 없는 리스트이다.

           2) 즉 연결리스트란 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 말한다.

 

- 연결리스트의 구조

 

 

 1) 상자를 컴퓨터 용어로 노드라고 부른다.

 2) 연결리스트는 이들 노드들의 집합이며, 노드들은 데이터를 저장하고 서로 연결되어 있다.

 3) 노드들은 메모리 어느 위치에나 있을수 있으며, 다른 노드로 이동하기 위해 현재 노드가 가지고 있는 

     포인터를 이용하면 된다.

 4) 노드는 위의 그림과 같이 데이터 필드와 링크필드로 구성되어 있다.

 

 

1) 연결리스트에서는 첫 번째 노드를 알아야만이 전체의 노드에 접근할 수 있다

2) 따라서 연결리스트마다 첫번째 노드를 가리키고 있는 변수가 필요한데 이를 헤드포인터라고 한다.

3) 그리고 연결리스트 마지막 노드의 링크 필드는 NULL로 설정되는데 이는 더 이상 연결된 노드가 

   없다는 것을 의미 한다.

 

- 장점과 단점

장점	단점
삽입, 삭제시 노드의 이동이 불필요하다. (배열은 이동이 필요)	배열에 비하여 탐색시간이 오래 걸린다. O(N)
추가 공간이 필요할 때 마다 동적으로 공간을 쉽게 추가 가능하다. (배열은 기존의 배열데이터를 복사하고, 새로운 큰 배열을 만들어 복사)	포인터 저장을 위한 추가적인 기억장소가 필요하다.

 

- 연결리스트의 종류

  1) 단순 연결 리스트 : 하나의 방향으로만 연결되어 있는 리스트이다. 마지막 노드의 링크 필드는 

                              NULL 값을 가진다.

  2) 원형 연결 리스트 : 단순 연결 리스트와 같으나 맨 마지막 노드의 링크 값이 첫 번째 노드를 

                              가리킨다는 것만 다르다.

  3) 이중 연결 리스트 : 각 노드마다 링크 필드가 2개씩 존재한다. 

                              (자신의 앞과 다음에 있는 노드를 가리키는 링크를 가진다.)

                    연결 리스트는 임용고시에서 좋아하는 주제 중 1가지 입니다.

                    기본적인 개념을 꼭 이해하고 넘어가시길 바랍니다.

                    다음 포스팅에서는 단순연결리스트에 대하여 알아보도록 하겠습니다.