리스트(List)

🧡 자료구조 및 알고리즘 스터디; 두 번째 주제 '리스트'

• 리스트는 Stack, Queue, Tree, Graph 등과 같은 다른 자료구조 구현에 활용될 기초 자료구조이다.
• 리스트는 데이터를 나란히 저장하고, 중복된 데이터의 저장을 허용한다.
• 자료구조에서 리스트는 구현방법에 따라 선형 리스트와 연결 리스트로 나뉜다.

🧐 일반적으로 사용하는 용어
(선형) 순차 리스트 = 선형 리스트
(선형) 연결 리스트 = 연결 리스트

💛 순차 리스트(Ordered List)

• 메모리의 저장 시작 위치부터 빈자리 없이 자료를 연속하여 저장한다.
• 우리가 표현하는 논리적인 순서와 실제 메모리에 저장되는 물리적인 순서가 같은 구조이다.
• 리스트에 나열한 데이터들이 일정한 순서를 가지며 인덱스를 사용하여 랜덤 엑세스가 가능하다.
• 신규 데이터의 삽입, 삭제가 발생하는 경우에도 빈자리 없이 순서대로 연속하여 저장되며, 순서를 다시 갱신해주어야 하기 때문에 데이터의 이동이 필요하여 오버헤드가 발생할 수 있다.

  🧐 오버헤드란?
  오버헤드란 프로그램 실행흐름에서 나타나는 현상 중 하나로 어떤 처리를 하기 위해 들어가는 간접적인 처리시간, 메모리를 의미한다.

- 순차 리스트는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 자료구조
- 탐색에는 효율적, 삽입/삭제 연산에는 비효율적
- 한 데이터를 삭제해도 배열은 연속해야 하므로 공간이 남아 메모리 낭비 초래

배열(Array)

• 같은 자료형을 가진 변수를 하나로 나타낸 것이다.
• 순차 리스트를 구현한 것이므로 연속된 메모리 공간으로 이루어져 있다.
• 기본적으로 크기를 바꿀 수 없는 정적 자료구조지만, 배열도 정적 배열(Static Array)과 동적 배열(Dynamic Array)이 있다.
• 배열의 크기를 변경할 수 있다는 차이 외에도 정적 배열은 선언된 블록이 끝나면 소멸되는 반면, 동적 배열은 프로그래머가 생성할 시점과 해체할 시점을 결정할 수 있다.
• 배열의 각 원소는 서로 인접해 있어 하나의 원소에 접근할 때 그 옆에 있는 원소도 캐시로 가져와 주변 원소에 접근할 때 빠르게 동작한다.(캐시 지역성)

  🧐 순차 리스트와 배열
  순차 리스트는 배열(Array)을 통해 구현할 수 있다.

💛 연결 리스트(Linked List)

• 메모리에 저장된 물리적 위치나 순서와 상관없이 링크에 의해 논리적인 순서를 구현하는 방식이다.
• 각 노드에 저장된 다음 노드의 주소에 의해 연결된 구조이다.
• 메모리가 연속된 주소일 필요가 없어 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.
• 인덱스가 없어 검색 성능이 좋지 않다.
• 포인터를 통해 다음 데이터의 위치를 가리키고 있어 데이터 삽입 또는 삭제 시 가리키는 주소만 변경하면 되므로 삽입/삭제가 용이하다.
• 길이가 가변적이며 포인터를 통해 다음 데이터의 위치를 가리키므로 추가적인 메모리 공간이 발생한다.

- 연결 리스트는 메모리의 동작 할당을 기반으로 구현된 리스트
- 탐색에는 비효율적, 삽입/삭제 연산에는 효율적
- 메모리 재활용이 용이하고 빈틈없는 데이터의 적재라는 장점을 취한 스트럭쳐

💚 순차 리스트와 연결 리스트의 삭제 동작 비교

• 순차 리스트
  삭제 시 순서 갱신 (주소와 인덱스 확인)
  
• 연결 리스트
  가리키는 주소만 변경 (다음 값 주소 확인)
  

💙 JAVA 의 리스트

자바는 배열과 리스트 모두 지원한다.

• 배열 ex) String[]
  배열을 이용하면 원소를 추가, 삭제, 변경하는 메소드를 직접 구현하여 사용해야 한다.
• 리스트 ex) ArrayList<>, LinkedList<>
  따라서 검색용으로는 ArrayList를, 삽입/삭제용으로는 LinkedList를 사용하는 것이 좋다.