리스트
값에 순서가 존재한다는 뜻이다.
간혹, 나도 그렇고 여러 사람이 처음 공부할때 헷갈릴텐데
리스트의 개념 과 리스트(배열) 를 착각 하는 경우가 많다.
알고리즘에서 얘기하는 리스트는 보통 배열이 아닌 리스트(순서가 있는 값의 집합) 이라고 생각하는게 편하다.
자, 그럼 우린 더이상 리스트와 링크드리스트의 차이를 찾아볼게 아니라 배열과 링크드리스트를 알아봐야함을 알 수 있다.
배열
배열은 첫번째 주소값으로 부터 바로 다음에 있는 순서의 주소값에 값들이 순서대로 저장되는것이다.
이미 다른 언어는 다루지않아봐서 잘 모르겠지만 필자의 주언어 인 자바스크립트를 기준으로
const testArray = ["하나", "둘", "셋", "넷", "다섯", "여섯", "일곱"];
라는 배열이 있다고 가정할때
"넷" 이라는 배열을 뽑기 위해서 findIndex, find, filter 등 배열메서드를 통해서 첫번째 인덱스부터 순차적으로 접근하여 값을 가져오거나 대괄호표기법인 testArray[3] 를 통해서 값을 뽑아올것이다. 이를 랜덤 엑세스 라고 한다.
복잡한 약속한 시간복잡도라는 얘기는 잠시 넘기고 내장메서드에 있는 반복문 findIndex, filter 등 두번째 파라미터에 오는 값을 콘솔로 찍어보면 알겠지만 무조건 index의 순서로 돌기때문에 첫번째부터 도는걸 알 수 있다. 그러므로 이미 선언되어있는 배열이나 Index별로 값이 정적으로 들어갈때에는 대괄호표기법(랜덤엑세스) 으로 접근하여 반복문을 돌지 않고 한 번에 찾는것이 이득임을 알 수 있다.
장점:
1. 값에 주소를 저장하지 않아 연결리스트에 비해 차지하는 용량이 적다.
2. 정적인배열인 구조인 경우 랜덤엑세스를 통해 간단하게 접근 할 수 있다.
3. 쉽게 값의 순서가 보장이 된다.
특징:
1. 물리적으로 주소값이 순서적으로 저장되어 있다.
각 구조의 장점만 보고 서로 다른 구조의 장점의 선택을 하면 되니 단점은 생략.
연결 리스트
연결리스트도 마찬가지로 순서가 있는 값의 집합이다. 다만 배열과 다른점은 순서를 어떻게 갖고 있는지의 차이가 있다.
각 노드의 자신이 갖는 값과 다음 노드를 가리키는 주소(포인터) 의 자료형태를 갖고있는 값의 집합.
주소값의 순서가 차례대로 나열되어있지는 않지만 각 노드의 값과 다음 순서의 주소와 함께 이루고있는 값의 집합이다.
우리는 이때 자바스크립트의 객체를 떠올릴 수 있을 것이다.
객체의 키값은 주소를 가리킨다. 키의 value에 다음 주소값(객체)을 넣어준다면? 그게 연결리스트다.
객체의 장점이 연결리스트의 장점과 직결된다고 볼 수 있다.
바로, 해쉬테이블을 통해 배열의 반복문처럼 하나하나 인덱스로 접근하지 않고 키로 바로 접근 할 수 있다.
배열에서는 배열의 0번째 인덱스인(head)와 마지막인덱스인(tail)만 접근하기 쉽지만 연결리스트에서는 키로 바로 접근하여 해당 주소값, 값만 바꿔주면 되니 배열보다 값의 수정이 쉽다.
장점:
1. 값의 수정이 간편하다.
2. 복잡한형태 ( ex) 정적인형태가 아닌 값 ) 값에 접근하기 위해 드는 비용이 적다 (해쉬테이블)
특징:
1. 논리적으로 주소값이 순서적으로 저장되어 있다.
