#1 리스트(List)

1. 리스트(List)

 리스트는 입력받은 데이터를 순차적으로 저장하는 가장 간단한 형태의 선형 자료구조이다.  리스트는 일반적으로

다음과 같은 기능을 가진다.

• 데이터 삽입
  • insert(e) : 데이터 e를 맨 뒤에 삽입 
  • insert(e, i) : 데이터 e를 인덱스 i에 삽입
• 데이터 삭제
  • delete(i) : 인덱스 i의 데이터 삭제
  • delete(e) : 데이터 e를 찾아 삭제
• 데이터 탐색
  • search(i) : 인덱스 i의 데이터 반환
  • search(e) : 데이터 e를 찾아 인덱스를 반환

이 외에도 구현자의 의도에 따라 리스트의 모든 요소를 제거, 리스트의 요소를 정렬, 리스트가 비어있는지 확인 등

다양한 기능이 들어가기도 하지만 가장 기본적인것은 위의 세 가지이다.

 

 

2. 리스트의 특징

• 구현이 간단하며 대부분의 프로그래밍 언어에서 기본 자료형 또는 내장 라이브러리의 형태로 지원
• 다수의 데이터를 순서를 유지한채로 그룹화하여 관리하기 좋음
• 특정 데이터를 탐색하는데 O(N) 의 시간복잡도를 보임 

 

3. 리스트의 구현 방식에 따른 특징

• 배열 리스트(Array List) : 배열을 기반으로 구현된 리스트
  • 인덱스를 활용하여 특정 순번의 데이터에 대해 O(1) 의 시간복잡도로 빠른 탐색이 가능
  • 삽입, 삭제 연산 실행 시 데이터들의 인덱스를 조정해야하기 때문에 O(N)의 시간복잡도를 보임
  • 배열의 크기에 제한이 있어 최초에 할당했던 크기 이상의 데이터를 삽입할 경우 배열을 확장하는
    과정을 거쳐야함

• 연결 리스트(Linked List) : 데이터를 하나의 노드로 구성하여 서로 연결시키는 것으로 구현된 리스트
  • n 번째 데이터에 접근하기 위해서는 링크를 타고 넘어가는 과정을 n번 거칠 필요가 있어 특정 순번의
    데이터를 탐색하는데 O(N)의 시간복잡도를 보임
  • 어느 위치에서 삽입/삭제 연산 실행 하더라도 새로운 노드를 만들어 전후의 연결관계만을 조정하면
    되기 때문에 O(1) 의 시간복잡도로 처리 가능
  • 데이터가 추가될 때마다 노드를 생성하기 때문에 데이터가 늘어나더라도 별도의 확장과정이 필요없음

 

4. 연결 리스트의 종류

• 단방향 연결 리스트
  • 각 노드가 데이터와 다음 노드의 주소로 이루어진 연결 리스트
  • 현재 노드에서 이전 노드를 참조할 수 없음
• 양방향 연결 리스트
  • 각 노드가 데이터와 이전 노드의 주소, 다음 노드의 주소로 이루어진 연결 리스트
  • 현재 노드의 이전 노드와 다음 노드를 모두 참조할 수 있음
• 원형 연결 리스트
  • 양방향 연결리스트의 첫 노드와 끝 노드를 서로 연결시킨 연결 리스트
  • 현재 탐색중인 노드를 가리키는 포인터 하나만으로 head와 tail을 모두 참조할 수 있는 것과 마찬가지
  • 스트림 버퍼나 큐를 구현하는데에도 사용 가능하며 데이터를 순환탐색하기에도 편리하다.