*🔐Study Keyword :

리스트의 종류인 어레이 리스트와 링크드 리스트에 대해 알아보자

리스트와 링크드 리스트

• 두 자료구조 모두 순서가 있는 자료, 데이터를 나열 및 저장한다는 점에선 거의 비슷하다.
• 그러나 배열과 연결 리스트는 엄연히 다르기 때문에 사용하기에 따라 프로그램의 성능이 달라지게 되므로 주의해야한다.

List

• 리스트란 어떤 순서가 있는 데이터의 집합을 의미한다.
  EX> 올림픽에서 마라톤을 했을 때 1등부터 들어온 순서대로의 결과를 저장하는 상황
• 이 리스트에는 2종류가 있다.

Array List

연속적인 공간에 순차적으로 데이터를 저장하여 indexing 가능하다.

• 배열은 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다.
  EX> 로또 번호를 뽑는다고 가정해보자, 4번부터 12,5,43,27... 이런식으로 뽑았다면

장점과 단점

인덱스를 가져 데이터 접근 속도(위치 탐색)가 빠른 반면 삽입/삭제에는 취약하다.

• 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 때문에 데이터 접근 속도가 매우 빠르다.
• 단, 배열은 데이터의 삽입/삭제에는 취약합니다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 한다.
• 배열은 사이즈가 고정되어있기 때문에 사이즈를 변경하기 위해선 복사해서 사용하여야한다.

Linked List

비연속적인 공간에 순서대로 데이터를 저장하며 링크드, 연결되어있는 형태이다.

• 연결 리스트는 데이터를 논리적 순서에 따라 데이터를 입력한다. 하지만 물리적 주소는 순차적이지 않음.
• 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있다.

장점과 단점

삽입/삭제가 쉽지만 위치 탐색이 오래 걸린다.

• 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 데이터 삽입/삭제는 용이하다.
• 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하여 배열에 비해 속도가 떨어진다.
• 데이터를 저장하는 공간과 데이터 외적으로 다음 데이터를 가리키는 정보를 저장하기 위한 추가적인 데이터 공간이 필요해 배열에 비해서 메모리를 더 많이 차지한다.

Array와 List의 차이

• Array는 연속적인 메모리에 같은 종류의 데이터를 저장할 수 있는 자료구조, 인덱스가 존재
• List는 순서를 가지며 추가, 삭제, 탐색이 가능한 ADT(abstract data type, 구조의 속성과 행위를 설명 EX>What에 대해 설명하지만 어떻게 동작하는 즉 how에 대해선 알려주지 않는 것)이다.
• Array는 무엇을 어떻게 하는지 명확하지만 List는 추상적이다.

ADT

• List는 add, remove, get, contains과 같은 오퍼레이션이 존재한다. 즉 오퍼레이션을 적용하는데 리시트가 무엇을 할 수 있는지 즉, 행위 what의 관점에서 설명한다. 이처럼 내부적으로 어떻게 구현하고있는지 설명하고 있지않은 것을 ADT라고한다.

그렇다면 어떻게 List를 구현할까?

• 크게 2가지로 Array나 Linked node를 사용해서 구현할 수 있다.
  자바엔 ArrayList에서 구현되고 LinkedList가 있다. 이 두 가지 모두 즉, ADT를 구현한 자료구조이다.
• 따라서 구현의 관점에서는 Array는 자료구조, List는 ADT라고 볼 수있다.

*💡conclusion

#📑Study Source

• 학습 자료, 쉬운 코딩 영상
• 이미지 출처