[자료구조] Linked List

 Linked List

 

1. 자기참조 구조체

 

struct student{

char name[10];

int score[4];

float avg;

struct student *p;     <-  구조체를 참조하는 포인터를 가졌음.

}

 

 

2. 일괄처리 가능

배열은 메모리가 붙어있기 때문에 일괄처리가 가능한 것이지만 리스트는 메모리가 붙어있지는 않다.

 

 

3. 메모리의 추가 삭제가 가능하다.

배열은 컴파일시에 메모리를 할당(정적메모리 할당)을 해야하기 때문에 메모리의 추가 삭제가 불가능 하지만

리스트는 동적메모리 할당을 이용해서 리스트를 연결시키고 끊음으로서 추가 삭제가 가능하다.

 

 

4. 종류

1) single linked list

2) double linked list

3)  single circular linked list

4) double circular linked list

 

 

5. 리스트에 사용되는 포인터

1) head pointer : 항상 첫번째 노드를 가르키는 포인터

2) new1 pointer : 새로운 것을 할당할때 사용하는 포인터

3) cur(커서) pointer : 모든 잡일을 하는 포인터

4) del pointer : 노드를 삭제할떄 사용하는 포인터

 

 

 

* 노드의 첫번째 즉, head포인터를 잃어버리면 절대로 다시 찾을 수 없기때문에 주의해야한다.

  (C언어에서는 동적할당시 포인터를 잃어버리면 프로그램이 종료되도 사라지지않는 좀비 메모리가 된다.)

  모든 노드는 첫번째 노드를 시작으로 노드를 추가하고 접근하기 때문에, 그 기준점이 사라지는 것은 큰 문제이다.