[Java] LinkedList 클래스

 

배열은 연속된 자료 구조를 구현한다. 

하지만 배열은 중간에 자료를 삽입하거나 삭제할 때 나머지 자료를 이동시켜 빈 공간을 만들지 못한다. 

이런 점을 개선한 자료 구조를 링크드 리스트(linked list)라고 한다. 

 

링크드 리스트의 각 요소는 다음 요소를 가리키는 주소 값을 가진다. 

 

 

따라서 물리적인 메모리는 떨어져 있어도 논리적으로 앞뒤 순서가 있을 수 있다. 

 

만약 A → B → D 가 순차적으로 저장된 링크드 리스트가 있다고 가정한다.   

 

 

리스트의 3번째 위치(B와 D사이)에 'C' 요소를 추가해 본다.

기존의 배열이라면 D를 뒤로 밀어내고 공간을 비워 그 자리에 C를 놓을 것이다.

하지만 링크드 리스트는 서로 가리키고 있는 주소 값만 변경해 주면 된다. 

B가 가리키던 다음 위치를 C로 변경하고, C가 가리키는 다음 위치를 D로 설정하면 된다. 

그러면 논리적으로 A → B → C → D 순서가 된다. 

 

 

만약 A → B → C → D 순서에서 'B'를 제거하고자 할 때도 각 요소가 가리키는 주소 값을 변경해 주면 된다.

A가 가리키는 다음 위치를 B가 아닌 C로 변경하기만 하면 A → C → D 순서가 된다. 

이때 제거된 B의 메모리는 자바의 가비지 컬렉터에 의해 수거된다. 

 

예제를 통해 LinkedList 클래스를 이해해 본다. 

 

package ch12_3;

import java.util.LinkedList;

public class LinkedListTest {
	public static void main(String[] args) {
		
		LinkedList<String> myList = new LinkedList<String>();
		
		// 링크드 리스트에 요소 추가
		myList.add("A");
		myList.add("B");
		myList.add("C");
		
		// 리스트 전체 출력
		System.out.println(myList);
		
		// 링크드 리스트의 첫 번째 위치에 D를 추가
		myList.add(1, "D");
		System.out.println(myList);
		
		// 연결 리스트의 맨 앞에 0을 추가
		myList.addFirst("0");
		System.out.println(myList);

		// 연결 리스트의 맨 뒤 요소를 삭제 
		myList.removeLast();
		System.out.println(myList);
	}
}