🥝 ADT,연결 리스트 (Linked List)

 

🥝 <추상 자료형 : Abstract Data Type>

 

'구체적인 기능의 완성과정(내부 동작 원리)를 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것'

 

▶추상적 자료형(ADT)은 구현 방법을 명시하고 있지 않다는 점에서 자료구조와 다릅니다.

 

 

쉽게 설명을 드리기 위해 지갑을 예로 들어볼게요.

 

지갑의 기능에는 무엇이 있는지 부터 생각해봅시다.

 

👉 지갑의 기능?👈

1. 카드의 삽입

2. 카드의 추출

3. 동전의 삽입

4. 동전의 추출

5. 지폐의 삽입

6. 지폐의 추출

 

지갑의 가격과, 무슨 가죽으로 만들었으며, 지갑을 만드는 공정 과정을 설명하지 않고,

오로지 지갑의 기능을 나열함으로써 정의를 하는 방식이라고 생각하면 쉽습니다. 

 

같은 방식으로 스택의 ADT에 대해서 설명을 해보겠습니다.

 

스택 : Stack

 

- FILO : First In Last Out

- 가장 최근에 들어온 것이 제일 먼저 나간다.

- push() : 스택에 요소를 추가하는 operation

- pop() : 스택에 요소를 제거하는 operation

...

 

ADT는 스택을 어떤 방식으로 내부 동작이 구현되는 지는 설명하지 않습니다. (자료 구조와의 차이점)

 

<배열을 이용한 리스트의 구현>

 

보통 " 리스트 = 연결 리스트? "  이러한 생각을 하는데 이는 사실이 아닙니다.

 

리스트 (List) 는 구현 방법에 따라 두 종류로 나눌 수 있습니다.

 

▶ 순차 리스트 : 배열을 기반으로 구현된 리스트

▶ 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

 

그럼 리스트 자료구조의 가장 기본적이고도 중요한 특성은 무엇일까요?

 

"리스트 자료구조는 데이터를 나란히 저장합니다. 그리고 중복된 데이터의 저장을 막지 않습니다."

 

그렇다면 리스트의 기능들을 정의해보겠습니다.

 

 

 

👉 배열 기반 리스트의 장점과 단점👈

▶ 배열 기반 리스트의 단점

- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.

- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

 

▶ 배열 기반 리스트의 장점

 

- 데이터의 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.