자료구조 - Linked List

Linked List란 ?

 

 노드와 노드를 순서대로 나열하는 선형적 구조의 자료구조 

 

 

 

Linked List는

 

- 단일 연결 리스트 (single linked list)

 

- 이중 연결 리스트 (double linked list)

 

- 환형 연결 리스트 (circular linked list)

 

로 크게 나뉘어짐.

 

 

 

일반적으로 

 

노드는 리스트의 원소 값(데이터)과

 

다음 원소를 가리키는 정보(포인터) // 여기까지가 (single linked list)

 

그리고 추가적으로 이전 노드의 메모리 주소를 저장하는 정보 (포인터)로 구성되어 있음. (double linked list)

 

 

환형 연결 리스트 (circular linked list) 는 

 

리스트의 마지막 노드가 첫번째 노드의 주소값을 가리키는 리스트의 형태를 나타냄.

 

 

 

여기서 배열과의 차이점은 
배열은 표현되는 순서가 물리적인 메모리 공간에서의 위치를 의미한다면 

 

리스트에서의 순서는 물리적인 메모리 저장 순서, 위치와 무관하게 원소간의 논리적인 순서만을 다룸.

 

 

 

리스트를 사용하는 이유 ? 

 

배열의 단점이 명확함.

 

 

- 10개의 데이터를 저장하는 배열을 만들었다고 가정할때
프로그램 동작 도중 이를 늘릴 방법이 없음. (컴파일 시간에 이미 배열의 갯수가 결정 나 있음)

 

 

- 10개의 데이터 중 하나를 중간에 삽입하고 삭제하기 불편함. 하나씩 당겨가거나 밀어줘야함.

 

 

- 메모리 할당과 해제를 수동으로 처리해야함.

 

 

- [] 연산자에서 배열 크기보다 큰 원소를 참조하는 것을 검사하지 못함.

 

 

- 배열을 중첩하면 문법 가독성이 많이 떨어짐.

 

 

 

따라서 

 

중간 데이터를 자주 삭제하거나 교체해야 할 경우 배열보다 리스트를 활용하는것이 효과적.

너무 큰 데이터를 저장하다보면 *메모리 단편화가 일어날 수 있으므로 주의 요망

 

 

 *메모리 단편화란 ? 

램에서 메모리의 공간이 작은 조각들로 나뉘어져 사용가능한 메모리가 분명히 존재하지만 할당이 불가능한 상태.