[자료구조] Linked List, Hash Table

1. Linked List (연결 리스트)

• 리스트의 첫번째 노드 'HEAD' , 리스트의 마지막 노드 'TAIL' TAIL 노드의 주소(레퍼런스)는 null이다.

• next : 마지막 노드를 가리키는 next pointer

• 각 노드는 (1) 현재 데이터, (2) 데이터의 주소(레퍼런스) 를 가진다. 

• 크기가 동적인 자료구조 (크기가 커지거나 작아질 수 있다.)

• 자료구조를 구성하는 요소 => 노드(Node)라고 부른다.

• 노드의 연결로 이루어진 자료 구조

• 연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 가짐

• 추가와 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과는 다르다.

• 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 가지지 않음

• 연결 리스트에서 검색하고자 할 때 전체 연결 리스트를 훑어야 하며, 이는 O(n) (선형 시간)의 복잡도를 필요로 함

• 길이 제한이 없다.

• 다른 데이터의 이동 없이 중간에 삽입이나 삭제가 가능하다.

 

1-1 . 단일 연결 리스트 (Singly Linked List)

: 한 방향으로 포인터가 다음 노드만 참조하는 구조이다.

 

1-2 . 양방향 연결 리스트 (Doubly Linked List)

: 양 방향의 두 포인터가 각각 이전과 다음 노드 참조하는 구조이다.

1-3 . 순환 연결 리스트 (Circular Linked List)

: 마지막 노드의 포인터가 첫 노드를 참조하여 첫 지점(head)으로 순환 가능한 구조이다.

 

 

 

Linked-list

 

# linked list real life example (실생활에서 생각해볼수 있는 연결 리스트)

바로 지하철역이다. 일방향으로 가고, 역에 도착할 때마다 다음 역을 말해 주는 게 연결 리스트와 비슷하다.

2호선 같은 경우는 환형(즉 순환)으로 되어 있는 연결 리스트이다.

이 외에도 멜론 등 음악을 듣는 플랫폼을 사용할 때, 다음 곡이나 이전 곡으로 갈 수 있는 것

포토샵처럼 ctrl + z 로 했던 것을 지우거나 ctrl + y 로 다시 나타내는 것,

이미지 뷰어처럼 다음 이미지, 이전 이미지를 볼 수 있게 할 수 있는것 들도 연결 리스트의 예이다.

 

속성

- head
- size

메소드

- addToTail(value) 주어진 값을 연결 리스트의 끝에 추가한다.
- remove(value) 주어진 값을 찾아서 연결을 해제(삭제)한다.
- getNodeAt(index) 주어진 인덱스의 노드를 찾아서 반환합니다(값이 아니라 노드).

해당 인덱스에 노드가 없다면 undefined를 반환한다.
- contains(value) 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환한다.
- indexOf(value) 주어진 값의 인덱스를 반환한다. 없을 경우 -1을 반환한다.

---

2. Hash Table (해시 테이블)

Hashing

:  매핑전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(Hash value) or 해시코드, 매핑하는 과정

• 해시 테이블은 키, 값 쌍을 지정하고 있는 자료 구조

• 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록,
  키를 "해시 함수(Hash function)라는 함수를 통해 특정 숫자값의 인덱스로 변환

• 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지

• 데이터가 저장되는 곳 : buckets

장점 : Hash Key를 가지고 배열의 인덱스로 사용하기 때문에 삽입, 삭제 검색이 빠름

단점 : Hash Function 사용하는데 추가적인 연산이 필요하며, 

함수 특성 상 중복되는 값으로 인해 해시 충돌(Hash Collision) 이 발생할 수 있다.

 

Hash Collision(해시 충돌) 방지