해나의 컴공생존기

연결리스트 (Linked List) - 데이터를 저장한 노트들을 포인터로 연결한 자료구조 - 동적인 자료구조 : 노트를 리스트에 추가하거나 제거함 - 생성, 탐색, 삽입, 삭제 가능 - 하나의 리스트의 각각의 노드는 연속된 공간이 아니라 힙 공간에 분산되어 위치된다. 장점 원소의 재배열이 쉽다 메모리의 낭비를 맞을 수 있다 (동적이기에) 단점 포인터를 위한 공간 소비 동적 메모리의 관리가 필요하다 리스트 중간의 원소로 직접 접근 불가 (순차접근 가능) 종류 단순 연결 리스트 이중 연결 리스트 환형 리스트 이중 환형 리스트 단순 연결 리스트 노드들을 일렬로 연결한 것 각 노트는 자료값과 다음 노드에 대한 포인터로 이루어짐 이전 노드를 바로 접근할 수 없다. CLinkedList::CLinkesList(){..

연결리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 저장하는 자료구조 특징 k 번째 원소를 확인하기 위해 O(k)가 필요하다 임의의 위치에 원소를 추가,제거는 O(1) 종류 단일 연결리스트 이중 연결리스트 원형 연결리스트 배열 vs 연결리스트 // 연결리스트에 원소를 넣었다가 뺏다하는 함수 #include using namespace std; const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; int unused = 1; void insert(int addr, int num) { dat[unused] = num; pre[unused] = addr; nxt[unused] = nxt[addr]; if(nxt[addr]!=-1) // 맨 끝에 삽입하는게 아..