[Java] Linked List (연결 리스트)

 

1. 단방향 연결리스트 vs 양방향 연결리스트

 

 

 

단방향 연결 리스트는 데이터값과 다음 노드의 주소값을 갖는다.

 

 

양방향 연결 리스트는 데이터값과 다음 노드의 주소값, 이전 노드의 주소값을 갖는다.

 

2. 노드의 추가, 삭제

A→C 의 연결리스트 사이에 B를 추가한다고 가정해보자.

A의 포인터는 B를 가리키고 B의 포인터는 C를 가리키도록 한다. 기존의 연결은 사라진다.

 

같은 원리로 노드를 삭제할 때에는 B가 가리키고 있던 C의 노드를 A에게 넘겨준다.

 

3. Java 구현

 

4. 실행

• 1의 값을 가진 head 노드를 생성하고
• 2추가 3추가 4추가 5추가
• 2삭제 3삭제
• 6추가
• retrieve(); 를 실행했다.

그 결과 1->4->5->6 으로 결과가 잘 나왔다.