오늘 배운 것

자료구조

1. Linked List

노드(Node)의 연결로 이루어진 자료구조

• 각 노드는 최소한 하나의 값과 다음 노드(포인터)를 가지고 있어야 한다.
• 따라서 각 노드는 Head 노드로부터 연결되어있고, 원하는 노드를 찾기 위해서는 Head 노드에서부터 Tail 노드까지 차례대로 탐색해야 한다. 따라서 O(n)의 시간 복잡도를 갖는다.
• 하지만 배열과는 다르게 노드를 삽입하거나 삭제하고자 할 때, 해당 노드를 이전 노드, 다음 노드와 이어주거나 삭제하기만 하면 되기때문에 O(1)의 시간복잡도를 갖는다.
• Linked List는 추가와 삭제가 빈번하고, 탐색은 자주 하지 않는 경우에 유용하게 쓰일 수 있다.

2. Hash Table

키(Key), 값(Value) 쌍을 저장하고 있는 자료구조

• Key와 Value를 입력하면, Key가 Hash Function을 통과해 Index값이 도출된다. 그러면 Index에 해당하는 Storage의 Bucket에 Value값이 저장되는 것이 Hash Table의 기본 메커니즘이다.
• Hash Table은 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠르게 검색할 수 있다. Hashing(키가 해시 함수를 통과해 나오는 과정)이후 Index 값이 나오고 Value가 저장되기 때문에, 해당 데이터에 접근하기 위해 필요한 것은 Index 뿐이다. 또한 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나, 삭제 시 다른 데이터로 채울 필요가 없다. 따라서 탐색, 삽입, 삭제의 시간복잡도는 모두 O(1)이다. 다만 해시충돌(Collision)을 해결하기 위해 다른 자료구조를 이용하면 시간복잡도는 변화한다.
• 만약 서로 다른 Key를 해싱한 값이 중복된다면 충돌(Collision)이 발생한다.
• 충돌은 주로 Chaining과 Open Addressing의 방법으로 해결한다.