#1 리스트(List)

#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) 의 시간복잡도로 처리 가능 데이터가 추가될 때마다 노드를 생성하기 때문에 데이터가 늘어나더라도 별도의 확장과정이 필요없음

연결 리스트의 경우 단방향 연결 리스트, 양방향 연결 리스트, 환형 연결 리스트 등 다양한 배리에이션이 존재하지만

기본적인 연산들에 관한 성질은 공유하기 때문에 별도로 다루지는 않기로 한다.

from http://scala0114.tistory.com/95 by ccl(A) rewrite - 2021-09-27 14:00:21