코딩꿀팁 - 자료 구조
1. 배열(Array)
배열은 가장 기본적인 자료 구조 중 하나입니다. 데이터들을 일렬로 나열하여 저장할 수 있으며, 각 데이터는 인덱스(Index)를 통해 접근할 수 있습니다. 데이터의 삽입과 삭제는 비효율적일 수 있지만, 데이터에 접근하는 속도는 빠른 편입니다. 배열은 메모리 상에 연속적으로 저장되기 때문에 캐시 효율이 좋고, 선형 탐색이나 정렬 알고리즘에 유용하게 사용됩니다.
2. 연결 리스트(Linked List)
연결 리스트는 다양한 크기의 데이터를 동적으로 저장하기 위한 자료 구조입니다. 각 데이터는 노드(Node)에 저장되고, 노드는 다음 노드를 가리키는 포인터를 갖고 있습니다. 삽입과 삭제가 상대적으로 효율적이지만, 데이터에 접근하는 속도는 느린 편입니다. 연결 리스트는 메모리 상에 노드가 분산되어 저장되기 때문에 포인터 참조에 따른 오버헤드가 발생합니다.
2-1. 단일 연결 리스트(Singly Linked List)
단일 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터만을 갖는 연결 리스트입니다. 노드의 삽입과 삭제는 상대적으로 쉽지만, 뒤에서부터 접근하는 것은 어렵습니다. 단일 연결 리스트는 Stack, Queue 등을 구현하는 데 유용하게 사용됩니다.
2-2. 이중 연결 리스트(Doubly Linked List)
이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 갖는 연결 리스트입니다. 노드의 삽입과 삭제가 비교적 어렵지만, 양방향으로 접근이 가능하므로 중간 노드의 삽입과 삭제를 효율적으로 수행할 수 있습니다. 이중 연결 리스트는 Linked List 기반의 자료 구조에서 유용하게 활용됩니다.
3. 스택(Stack)
스택은 데이터를 순서대로 저장하고, 가장 최근에 삽입한 데이터를 가장 먼저 꺼내는 자료 구조입니다. 후입선출(LIFO: Last In, First Out) 구조를 갖고 있으며, 데이터의 삽입과 삭제가 상수 시간에 이루어집니다. 스택은 함수 호출이나 괄호 검사, 미로 찾기 등에 유용하게 사용됩니다.
4. 큐(Queue)
큐는 데이터를 순서대로 저장하고, 가장 먼저 삽입한 데이터를 가장 먼저 꺼내는 자료 구조입니다. 선입선출(FIFO: First In, First Out) 구조를 갖고 있으며, 데이터의 삽입과 삭제가 상수 시간에 이루어집니다. 큐는 프로세스 스케줄링, 너비 우선 탐색 등에 유용하게 사용됩니다.