1. linked list

Linked List는 Array List와는 다르게 요소와 요소 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미. (참고 링크)

데이터 변경(삽입, 삭제)에는 높은 성능을 보이나, 조회 및 캐싱의 경우 성능이 떨어진다는 특징을 가지고 있다.

생활코딩 링크

- list

특징

• 사이즈가 고정되어 있고(=메모리에 할당), 인덱스로 값을 탐색함
• 연속적인 묶음으로 저장되어 조회에 용이

단점

• 삽입, 삭제 시 인덱스가 변경되어 빈 값을 채워주는 부가적 연산이 필요함. 삽입, 삭제가 빈번한 프로세스의 경우 치명적
• 크기가 한정되어 있어 재조정할 경우 상당한 연산량이 요구됨

- linked list

구성요소

특징

• 사이즈가 무한하고(메모리 용량이 무한할 경우), link field(참조자, 포인터)로 다음 노드를 알 수 있음
• 연결 연결되어 있는 구조이기 때문에 순차 접근만 가능
• 주소만 연결하면 되기 때문에 삽입, 삭제가 리스트에 비해 빠르고 쉬움

단점

• 불연속적 단위로 저장되기 때문에 조회에 불리, 포인터로 인해 저장공간을 더 쓰게됨

2. hash table

key-value 1:1 매핑에 사용되는 자료 구조. 해시 테이블은 해시 함수를 사용해 인덱스를 저장소(버킷, 슬롯)의 배열로 계산한다. 이 때 value를 알고 싶으면 key값을 해시함수를 써서 인덱스를 구하면 되기 때문에 탐색에 유리하다.

- 구성요소

해시 함수

• 키값을 해시로 바꿔주는 역할.
• 키값의 길이를 단일화시켜 저장소를 효율적으로 운영할 수 있음
• 서로 다른 키가 같은 해시를 가질 경우 해시 충돌이 생겨, 이를 방지할 수 있어야 함

해시

• 해시 함수의 결과물로, 저장소에 값과 같이 매칭되어 저장됨
• 인덱스값이 불규칙함

- 특징

장점

key값으로 value를 빠르게 접근, 조작 가능

단점

• 순서가 있는 배열에는 어울리지 않음
• 공간 효율성이 떨어짐
• 해시 함수 의존도가 높음