[ 11강 ] 연결리스트 (Linked List)

연결리스트 (Linked List)

- 데이터를 저장한 노트들을 포인터로 연결한 자료구조

- 동적인 자료구조 : 노트를 리스트에 추가하거나 제거함

- 생성, 탐색, 삽입, 삭제 가능

- 하나의 리스트의 각각의 노드는 연속된 공간이 아니라 힙 공간에 분산되어 위치된다.

 

장점 

원소의 재배열이 쉽다

메모리의 낭비를 맞을 수 있다 (동적이기에)

 

단점

포인터를 위한 공간 소비

동적 메모리의 관리가 필요하다

리스트 중간의 원소로 직접 접근 불가 (순차접근 가능)

 

종류

단순 연결 리스트

이중 연결 리스트

환형 리스트

이중 환형 리스트

 

단순 연결 리스트

노드들을 일렬로 연결한 것

각 노트는 자료값과 다음 노드에 대한 포인터로 이루어짐

이전 노드를 바로 접근할 수 없다.

 

CLinkedList::CLinkesList(){

	head = new CNode();
    tail = new CNode();
    head->setNext(tail); 
    tail->setNext(tail);
    
}