22.01.15(토)

미션과 수업으로 학습한 자료구조 관련 List 내용을 정리하고자 한다.

1. 단일 연결 리스트

• 노드안에 해당 노드를 가리키는 값과 다음 노드를 가리키는 주소값을 가지고 있고 단방향으로 진행되는 리스트를 의미한다.

  장점 : 연산이 단순하여 데이터 추가 삭제 시 0(1)의 시간복잡도를 가짐.
  단점 : 특정 위치의 배열 검색 시 0(n)의 시간이 걸림.

2. 이중 연결 리스트

• 노드안에 해당 노드를 가리키는 값과 다음 노드를 가리키는 주소값, 그리고 이전 노드를 가리키는 주소값 2개를 가지고 있어 양방향으로 진행되는 리스트를 의미한다.

  장점 : 데이터 삭제 시, 이전 노드와 다음 노드를 연결해주기 위해 이전 노드를 찾기위해 검색을 한번 더 필요하지만 이중 연결은 이전 노드를 가리키는 주소값이 있으므로 삭제 시 탐색이 불필요하다.
  단점 : 단일 연결보다 메모리를 더 쓴다.

3.선형 리스트

• 데이터를 논리적인 순서대로 메모리에 연속하여 저장, 구현하는 방식. 데이터의 개수가 고정되어 선언되며 배열을 이용해 구현한다.

  장점 : 인덱스로 접근하기 때문에 접근 속도가 매우 빨라, 원소 검색의 시간복잡도는 O(1)이다.
  단점 : 데이터의 개수가 고정되어 있기 때문에 배열의 크기와 데이터의 수가 상이할때 메모리 공간 낭비 혹은, 저장 불가한 상황이 발생할 수 있다. 그리고 원소 삽입 삭제 시 연속배열이 갖는 단점 특성을 가지고 있다.

4. 환형 리스트

• 단일 연결리스트와 비슷하지만, 마지막 노드가 리스트의 첫번째 노드를 가리키게 하여, 방향을 단방향에서 원형으로 변경한 리스트이다.

  장점 : 단일 연결 리스트에서 이전 노드에 접근 시 탐색을 한번 더 하던 번거로움을, 순환을 통해 다시 접근 할 수 있도록 개선하였다.
  단점 : 다만, 순환이라 탐색은 필요하지 않지만 이전 노드에 접근 시 한바퀴를 순회해야 한다는 문제점이 있다.