연결 리스트 - 싱글 링크드 리스트(Linked List)

싱글 링크드 리스트(Single Linked-List)

- 싱글 링크드 리스트는 노드의 순서로 구성된 구체적인 데이터 구조이다.

- 각 노드는 data를 저장하는 element와 , 다음 노드의 주소를 연결하는 링크 필드로 구성되어 있다.

코드로 나타낸다면 다음과 같이 나타낼 수 있다.

struct Node {
	int data;
	Node* next;
};

 

Head(맨 앞 노드)에 Inserting(삽입) 방법

- 새 노드를 할당한다 -> 새 data를 삽입한다. -> 직전 Head에 새 주소를 가르킨다. -> 새 노드의 Head를 업데이트한다.

 

Head(맨 앞 노드)에 Removing(제거) 방법

- Head 노드의 주소를 다음 주소로 변경한다. -> 가비지 컬렉터가 이전 노드를 회수하도록 허락한다.

 

Tail(맨 뒤 노드)에 Inserting(삽입) 방법

- 새 노드를 할당한다 -> 새 data를 삽입한다. -> 새 노드의 주소를 NULL을 가르킨다. -> 삽입 전에 존재하던 마지막 노드를 새 노드를 가르키게 한다. -> 새 노드의 Tail 주소를 업데이트 한다.

 

Tail(맨 뒤 노드)에 Removing(제거)

- 싱글 링크드리스트에서 맨 뒤 노드를 제거하는 것은 효율적이지 않다.