자료구조02_리스트
정의
컴퓨터 과학에서 같은 값이 한 번 이상 존재할 수 있는 일련의 값이 모여있는 추상 자료형 (이하ADT)
시퀀스(sequence)라고도 부른다.
순서를 가지며 추가, 삭제, 탐색 가능한 객체의 집합으로 원소들이 연속적으로 저장되는 형태의 추상 자료형
※자료구조와 추상자료형 참고 https://crashcoding.tistory.com/11
기능 정의
연속적인 임의 개체들을 모델링한다.
각 원소는 다른 자료형을 가질 수 있다.
원소에 대한 접근은 순위rank를 이용한다.
참고
다음으로 '사용할 프로퍼티'나 '리스트가 수행할 동작'이 서술되는데 주로 추가, 삭제, 수정, 탐색 등이다.
수많은 프로그래밍 언어들은 리스트 자료형을 지원하며
리스트와 리스트 조작을 위한 특수한 문법과 시맨틱을 갖추고 있다.
즉 이미 리스트를 구현해 두었다는 의미다.
리스트를 직접 만들어 보고 싶은 게 아니라면
각 언어에서 리스트를 어떻게 사용해야 하는지 찾아보고 사용하면 된다.
공식문서에 나와있다.
https://docs.python.org/ko/3/tutorial/datastructures.html
특징
자료를 순서대로 한 줄로 저장
여러 자료가 일직선으로 서로 연결된 선형 구조
제일 처음 데이터를 가리켜서 Head
제일 마지막 데이터를 가리켜서 Tail
장점(구현 방법에 따라 차이 있음)
빈틈없이 데이터를 저장할 수 있다.
삽입 삭제의 용이.
동적이므로 크기가 정해져 있지 않다.
메모리의 재사용 편리
불연속적이므로 메모리 관리의 편리
다른 자료형도 취급 가능
단점(구현 방법에 따라 차이 있음)
검색 성능이 좋지 않다.
추가적인 메모리 공간 발생.
배열과 비교
리스트는 배열과 유사한 느낌을 갖고 있다.
분명 배열과 다른 목적을 두고 설계되었기 때문에 배열보다 좋은 점도 있고 나쁜 점도 있다.
그래서 배열과 비교해서 알아두는 것이 좋다.
배열 : 데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어나지 않으며 검색을 필요로 할 때 유리.
리스트 : 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.
종류
리스트는 구현 방법에 따라 Array List와 Linked List로 나눌 수 있다.
핵심은 데이터를 저장하는 공간의 연속/비연속이다.
구현
리스트 자료형은 배열 자료 구조나 포인터와 구조체를 이용한 객체를 사용하여 구현되기도 하지만
일부 목적에는 다른 자료 구조를 사용하는 것이 더 적절할 수도 있다.
Array List
이름처럼 배열로 구현되었다. 그래서 데이터의 순서가 메모리에 물리적인 순서대로 저장된다.
배열의 특성을 이용할 수 있는데 이는 배열의 장점과 단점을 그래도 물려받는다고도 할 수 있다.
물론 배열의 장점 중 하나인 index 또한 사용할 수 있다.
여기서 의문이 하나 생긴다.
배열은 한번 공간을 할당하면 공간 이상으로 데이터를 추가할 수 없는 반면
리스트는 추가, 삭제, 탐색이 가능해야 한다. 또한 배열은 선언할 때 공간 크기를 지정하는데,
리스트는 선언 시 공간 크기를 지정하지 않는다.
이런 점을 어떻게 극복했는지 살펴보자
동적 배열
초깃값을 작게 잡아 배열을 생성하고, 배열이 꽉 채워지면 크기를 2배로 늘리는 방식(더블링)
일종의 트릭이다.
때문에 초기 선언 시 사용자가 리스트의 크기를 지정하지 않아도 알아서 크기가 작은 배열을 생성한다.
일반적인 개념의 배열인 C언어의 배열과 달리 파이썬의 리스트는 동적 배열로 동작한다.
1. 리스트 선언 시 내부적으로 작은 크기의 배열 생성 ex) 크기가 4인 배열 생성
2. 크기가 다 채워졌을 경우 기존 크기의 2배에 해당하는 공간 생성 ex) 크기가 8인 배열 생성
3. 기존 배열의 내용을 신규 배열로 복사 후 데이터 추가
삭제의 경우도 마찬가지이다.
데이터가 절반 이하로 줄면 절반의 크기만큼 따로 공간을 생성하고 데이터를 복사한다.
장점
검색 속도가 빠르다
단점
데이터의 추가 삭제가 느리다
Linked List
배열로 구현된 Array List와 다르게 구조체와 포인터로 구현된다.
때문에 리스트 ADT에서 요구하는 것을 모두 구현할 수 있지만
데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다는 특징이 있다.
단순히 리스트 ADT를 구현하는 방식을 넘어서 다양한 ADT구현의 기반이 되는
기본적이고 대표적인 자료구조가 되었다.
장점
데이터 입력 시 주소가 순차적이지 않아 요소를 메모리의 어느 곳에 나 둘 수 있음 (크기가 동적임)
메모리 관리 쉬움
인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하는 형태로, 요소 중간에 삽입, 삭제 시 논리적 주소만 바꿔주면 되기 때문에 요소(데이터) 삽입, 삭제가 용이
단점
요소에 바로 접근 불가
연결되어 있는 링크를 따라가야만 접근이 가능. (접근 속도 느림)
어떤 자료구조인지에 따라서 장점과 단점이 명확하므로 그 성능의 차이가 발생한다.
어떤 프로그램인지 잘 알아야 그에 맞는 적합한 자료구조를 선택할 수 있기 때문에
우리는 프로그램의 특성을 잘 생각해볼 수 있어야 한다.
referrence
https://ko.wikipedia.org/wiki/%EB%A6%AC%EC%8A%A4%ED%8A%B8_(%EC%BB%B4%ED%93%A8%ED%8C%85)
https://comdoc.tistory.com/entry/2-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EC%B6%94%EC%83%81-%EC%9E%90%EB%A3%8C%ED%98%95List-ADT-with-Python
https://interconnection.tistory.com/104
https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8