단순연결 리스트(singy linked list)

단순연결 리스트(singy linked list)

연결된 자료구조는 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 이 경우 서로 다른 메모리 위치에 데이터가 저장됩니다.

단순 연결리스트 기본 구조

이 그림과 같이 구성된 자료구조를 연결 리스트라고 합니다. 연결 리스트의 기본 구조에서 각각의 노드는 저장할 데이터와 다음 노드를 가리키는 포인터(next)를 가리키고 있습니다. 맨 마지막 노드에서는 다음 노드의 포인터 대신 자료구조의 끝을 나타내는 null을 가집니다.

데이터 접근 시 헤드(head)부분부터 시작하여 원하는 원소에 도달할 때까지 next포인터를 따라 이동해야 합니다. 그러므로 i번째 원소에 접근하려면 연결 리스트 내부를 i번 이동하는 작업이 필요합니다. 원소 접근 시간은 o(n)입니다.

연결 리스트에 새 원소 추가하기

i=1 과 i=3의 사이에 새로운 노드 i=2를 추가하는 과정

새로운 원소를 삽입하려면 새로운 노드를 생성하고, 각 노드의 next 포인터를 수정합니다. 새로 추가한 노드(i=2)가 다음 노드(i=3)을 가리키게 만듭니다. 이전 노드(i=1)이 다음 노드(i=3)을 가리키던 것을 제거하고 새로운 노드(i=2)를 가리키게 설정합니다.

C++에서는 std::array를 제공합니다.

std::array는 메모리를 자동으로 할당하고 해제합니다. std::array는 원소의 타입과 배열 크기를 매개변수로 사용하는 클래스 템플릿입니다.

#include #include using namespace std; int main() { array arr1; arr1[0] = 1; cout << "arr1 배열의 첫 번째 원소: " << arr1[0] << std::endl; array arr2 = { 1,2,3,4 }; cout << "arr2의 모든 원소 : "; for (int i = 0; i < arr2.size(); i++) { cout << arr2[i] << " "; } cout << endl; return 0; }

범위기반 for문을 이용하여 출력하는 방법

#include #include using namespace std; int main() { array arr = { 1,2,3,4,5 }; for (auto element : arr) { cout << element << ' '; } return 0; }

배열의 크기를 반복문에게 알리지 않고도 실행이 가능한 이유는 std::array는 begin()과 end()라는 이름의 멤버 함수를 제공하며, 가장 첫 번째 원소와 가장 마지막 원소의 위치(정확하게는 마지막 원소 다음 위치)를 반환합니다.

범위 기반 for 반복문은 begin()위치부터 시작하여 증가 연산자를 통해 차례대로 워ㅏㄴ소를 이동하다가 end() 위치에 도달하면 종료합니다.

iterator를 사용하여 array를 출력하는 방법

#include #include using namespace std; int main() { array arr = { 1,2,3,4,5 }; for (auto it = arr.begin(); it != arr.end(); it++) { auto element = (*it); cout << element << ' '; } return 0; }

iterator를 array(begin()의 반환 값) 의 시작원소로 초기화한후에 array의 마지막원소 + 1(end()의 반환 값) 의 위치가 아닐 때까지 출력합니다.

from http://cdsd1234.tistory.com/103 by ccl(A) rewrite - 2021-12-20 01:00:50