[자료구조] Array, Vector, Linked List의 차이

ADT: Linked List,
Not ADT: Array, Vector(≒ Dynamic Array)

ADT
순수하게 기능이 무엇인지를 나열한 것을 가리켜 '추상 자료형' 혹은 ADT라고 한다.
특정 자료형과 그 자료형을 바탕으로 하는 기능들(함수들)의 집합이라고 생각하자.
자료구조에 앞서 ADT를 알아야 하는 이유.
자료구조의 간단한 예로 연결리스트, 스택을 들어보면
연결리스트는 insert, delete 등과 같은 기능들(함수)과 함께 작동하는 자료구조이다.
스택 역시 push, pop. peek, empty 등과 같은 기능들(함수)과 같이 정의되어야 비로소 작동하게 된다.
그렇기에 자료구조(연결리스트, 스택, 큐 등)의 ADT는
data를 담을 저장소를 만드는 것과
data를 다루는 함수들을 정의하는 것을
포함하는 개념인 것이다.

https://velog.io/@hwan2da/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%B6%94%EC%83%81%EC%9E%90%EB%A3%8C%ED%98%95

 

ADT 관점에서 List

List

• 값(value)들을 저장하는 추상자료형(ADT)
• 순서가 있음
• 중복을 허용

 

List 구현체

List를 실제로 구현하는 방법들을 살펴보자.
List 구현체에는 대표적으로 2가지가 있다.

1. Array
  1`. Dynamic Array (Vector)
2. Linked list

 

Array List와 Linked list의 가장 큰 차이

메모리에 어떻게 저장되느냐가 가장 큰 차이다.
Array:
배열을 써서 연속적인 메모리 공간에 데이터를 저장
Linked list:
노드 각각이 포인트를 통해서 다음 노드를 가리키는 형태이기 때문에 매모리 공간상에서 따로따로 저장이 된다.

 

https://velog.io/@rlaugs15/%EB%B0%B0%EC%97%B4%EA%B3%BC-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EA%B0%9C%EB%85%90%EA%B3%BC-%EC%B0%A8%EC%9D%B4

array list와 linked list의 개념과 차이