[자료 구조] 연결리스트, 배열, 벡터

💡 연결 리스트 (Linked List)

• 연결 리스트는 여러 개의 노드들이 순차적으로 연결된 효율적인 형태를 갖는 자료구조
• 첫번째 노드 = head, 마지막 노드 = tail
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 ****이루어져 있음
• 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이함
• Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러난다.

✅ 연결 리스트의 시간 복잡도

• 탐색 : O(n)
• 삽입 / 삭제 : 삽입과 삭제 자체는 O(1)
  • 연결 리스트의 처음 삽입/삭제 : O(1)
  • 연결 리스트 중간 삽입/삭제 : O(n) (탐색 시간 소요)
  • 연결 리스트 끝 삽입/삭제 :
    • 끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
    • 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) (탐색 시간 소요)

 

✅ 연결 리스트 종류

• 싱글 연결 리스트 : next 포인터만 가진다.
• 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
• 원형 이중 연결 리스트 : 이중연결리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.

---

💡 배열(Array)

• 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료 구조
• 메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 때문에, index를 통한 접근이 용이
• 배열의 크기는 처음 생성할 때 정하며 이후 배열의 크기를 변경할 수 없다.
• 같은 타입의 변수들로 이루어져있다.
• 중복 허용

 

✅ 배열의 시간 복잡도

• 탐색 : O(1). 단, 접근하고자 하는 인덱스를 알고 있어야 한다.
• 순차적으로 탐색시에는 O(n).
• 삽입 / 삭제 :
  • 배열의 처음 또는 중간에 삽입 및 삭제 : O(n). (삽입 지점 이후의 데이터를 옮겨야 하기 때문)
  • 배열의 끝에 삽입 및 삭제 O(1)

 

✅ 배열과 연결리스트 비교

 

 

💡 벡터

• 벡터는 동적으로 요소를 할당할 수 있는 동적 배열입니다.
• 컴파일 시점에서 개수를 모른다면 벡터를 사용하면 됩니다.
• 중복을 허용하고 순서가 있고 랜덤 접근이 가능합니다.

push_back() : 뒤에서부터 요소를 더함

pop_back() : 맨 뒤부터 지움

erase() : 지우기

find() : 요소 찾기

clear() : 배열 초기화

 

장점

• 마지막 위치에 추가나 삭제 쉬움
• 구현 용이
• 랜덤적으로 직접 접근 가능

단점

• 중간에 삽입 삭제가 많은 상황에서 비효율적

---