이 게시글은
서울대학교 데이터사이언스대학원
조요한 교수님의
데이터사이언스 응용을 위한 컴퓨팅 강의를
학습을 위해 재구성하였습니다.
Array와 Linked List 비교
array와 linked list의 구조
array는 우리가 흔히 알고있는
[1, 2, 3, 4, 5]
같은 자료구조이다.
위에서 보이듯이 array는 연속된 공간을 할당받고
그래서 실제로 1과 2가 저장된 공간도
물리적으로 연속되어 있다.
linked list는 영어 그대로
데이터들이 서로 연결되어있는 list라고
생각하면 편하다
Linked list에 1, 2, 3, 4, 5가 있다고 하면
각 1, 2, 3, 4, 5가 메모리 어디에 저장되어있는지는 모르지만
1과 2가 연결되어있고
1이라는 데이터와 함께 2가 저장된 메모리의 주소를
함께 저장하기 때문에
1에 접근하면 2에도 접근할 수 있는 방식의 자료구조이다.
따라서 연속된 공간을 할당받는 array와 달리
linked list는 인접한 element들 간에
physical한 공간은 붙어있지 않고
linked list는 다음 메모리가 가리키는 곳을
포인터로 연결한다.
array와 linked list의 element 접근 방식 & 메모리사용
array는 연속적으로 할당되어있기 때문에
특정 데이터가 저장되어있는 위치로 접근할 수 있다.
이를 인덱스라고 하는데
예를 들어
num = [1, 2, 3, 4, 5]
라는 array가 있으면
num이라는 array의 첫번째 요소에 접근하고 싶으면
num[0] <- 이런 방식으로 접근해주면 된다
이런방식으로 접근이 가능한 것을
random access가 가능하다고 표현한다
그리고 당연히 element에 접근하는 속도도 빠르다
반면에, linked list는 random access가 불가능하다
내가 원하는 element를 찾고싶다면
처음 element부터 접근해서 하나씩 하나씩 순차적으로 따라가
내가 원하는 element를 찾아야한다
당연히 element에 접근하는 속도가 느릴 것이다
또한, array는 element 한 개만 메모리에 저장하면 되지만
linked list같은 경우는 element와 다음 element의 주소를 담은
포인터까지 담아야하기 때문에 메모리 측면에서도
linked list가 array에 비해 더 효율성이 낮다
이렇게 보면 linked list보다 array가 훨씬 좋은 것 같은데
왜 linked list를 사용해야하는 경우가 발생하는 것일까?
insertion과 deletion
array는 element들의 삽입과 삭제가 어렵다
요소들이 일렬로 정렬되어있다보니
기존 array에서 새로운 element를 삽입하려면
새로 삽입된 요소 이후의 요소들을 다 뒤로 한 칸씩 밀어야하고,
기존 array에 있는 어떤 요소를 삭제하려면
삭제된 요소 뒤에 있는 요소들을 앞으로 한 칸 당겨줘야한다
그래야 연속으로 정렬된 array에 빈 공간이 생기지 않게
element들이 들어설 것이다
반면에 Linked list는 반드시 연속된 공간에
요소들이 할당되어야하는 것이 아니기 때문에
삽입과 삭제가 간편하다
새로운 요소를 삽입하려면 그저 삽입하고 싶은 요소와
포인터 변수로 앞 뒤 요소의 주소값만 설정해주면 된다
element 삭제도 마찬가지
또한, array같은 경우는 공간 resizing이 힘들다는 단점도 있다
이게 무슨 말이냐면
보통 array를 정의할 때는 array의 길이를 함께 정의해준다
이처럼 고정된 길이인 fixed length로 정의해주기때문에
프로그래밍 도중, array의 길이가 변경되어야하는 경우
또 새롭게 정의하고, 새롭게 정의된 길이만큼 연속된 메모리 공간을 찾아
기존 요소들을 그대로 옮겨주는 복잡한 과정이 필요하게 되는 것이다
정리
따라서 이러한 array와 Linked list의 장단점때문에
보통 array는 삽입과 삭제가 적고 사이즈가 작은 데이터에 적합하고
linked list는 삽입과 삭제가 잦은 데이터에 적합하다
또한 linked list 같은 경우는
많이 사용하는 요소들은 캐싱한다던지
sentinel node와 같이 마지막 노드를 추적하는 등
다양한 기법으로 단점을 극복할 수 있다고 한다
Queue
큐는 우리 흔히 말하는 줄서는걸 생각하면 된다
데이터들이 한쪽방향으로 들어와서 한 쪽 방향으로 나가는 구조이다
데이터가 들어오는 입구와 나가는 출구가 다르며
먼저 들어오는 데이터가 먼저 나가는 구조이기 때문에
First in First out (FIFO)라고 부른다
흔히말하는 선입선출의 구조이다
Stack
스택은 데이터가 들어온 방향으로 다시 나가는 구조이다
데이터가 들어오는 입구와 나가는 출구가 같으며
하나하나 차곡차곡 쌓였다가 빠지는 구조라고 생각하면 좋다
가장 늦게 들어온 데이터가 가장 빨리 나가기 때문에
List in First out (LIFO)라고 부르며
ctrl+z와같은 undo function에 사용되는
대표적인 자료구조이다
가장 최근에 수행했던 것을 가장 먼저 취소하기때문이다
Q) Queue와 Stack을 구현하기 위해서 array가 적합할까 Linked list가 적합할까?
A) 정답은 없다. array든 linked list든 구현가능하다. 하지만 더 효율적인 방법은 있을 것이다
Queue -> 한쪽방향으로 들어와서 한쪽 방향으로 빠지기 때문에 element들의 위치가
지속적으로 바뀌게 되므로 linked list가 더 효율적일 것
Stack -> 가장 마지막 부분을 입구와 출구로 두어 element를 관리할 수 있기 때문에
resizing의 필요가 없어 array가 더 효율적일 것
Hash Tables
Hash Table은 데이터를
key-value pairs로 저장하는 데이터구조이다
각 entries들의 index를 저장하고 있고
이 Index들이 각각의 key와 매칭이 되는데
이를 해싱(hashing)한다고 표현한다
예시를 들어 설명하면 더욱 좋을 것 같다
"신짜오"라는 이름이라는 key를 갖고
value로 "신짜오"의 나이인 27을 저장하고 싶다
그렇다면
put("신짜오", 27) 이렇게 전달해주면
"신짜오"라는 key가
key를 보고 index를 생성해주는 해시함수(hash function)에 전달된다
그렇다면 "신짜오"라는 key는 해시함수를 통해서
1이라는 index를 반환받는다
그렇게되면 배열의 1번 인덱스에 value값인 27이 저장이 되는 것이다
나중에 "신짜오"라는 key를 이용해서 value를 불러오고 싶다면
get("신짜오")로 호출해주면
"신짜오"라는 key는 인덱스인 1을 반환하고
반환된 1 인덱스를 통해 배열의 자리에 들어가서
27의 value를 가져오게 되는 것이다
어쩔수없이 entries가 많아지게되면
하나의 index에 여러개의 entry가 저장되게되는데
이를 해시충돌(hash collision)이라고 한다