Linkedlist에 대해 알아보자

지난 시간에 살펴본 Arraylist에는 치명적인 단점이 하나 있습니다.

놀이기구를 타려고 줄을 서 있는데, 한 명이 새치기를 하게 되면 그 뒤에 서 있던 모든 사람이 한 칸씩 뒤로 순서가 밀리는 비효율이 발생하게 됩니다.

이처럼, 배열 사이에 새로운 값을 추가해 넣으려면 너무 많은 메모리 낭비가 발생합니다.

Linkedlist(연결 리스트)는 이런 단점을 해결하기 위해 탄생했습니다.

(가독성을 위해 줄을 맞추긴 했지만) 저장된 요소가 비순차적으로 분포할 수 있고, 이들을 링크로 연결합니다.

저장할 값과 함께 뒤에 올 값의 메모리 번호를 노드에 저장하여, 두 요소를 굳이 붙여 놓지 않아도 다음 값의 메모리 번호만 잊지 않는다면 서로를 소환해서 연결할 수 있습니다.

새로운 값의 추가나 제거도 Arraylist보다 쉽습니다.

코드와 도표로 함께 살펴보겠습니다.

package jaryogujo;
import java.util.*;
public class Linkedlist {

	public static void main(String[] args) {
		LinkedList<String> lnkList = new LinkedList<String>();
		// add() 메소드를 이용한 요소의 저장
		lnkList.add("넷");
		lnkList.add("둘");
		lnkList.add("셋");
		lnkList.add("하나");

		// for 문과 get() 메소드를 이용한 요소의 출력
		for (int i = 0; i < lnkList.size(); i++) {
		    System.out.print(lnkList.get(i) + " ");
}

(작은 정사각형이 해당 블록의 메모리 주소입니다.) 다음과 같이 linkedlist에 요소를 추가했습니다.

그 결과가 다음과 같습니다.

// remove() 메소드를 이용한 요소의 제거
		lnkList.remove(1);

		// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
		for (String e : lnkList) {
		    System.out.print(e + " ");
}

Remove() 메서드를 사용하여 1번지에 저장된 ‘둘’ 을 제거했습니다.

(넷, 셋, 하나) 만 남게 되겠죠.

lnkList.set(2, "둘");

		for (String e : lnkList) {
		    System.out.print(e + " ");
}

다음으로, 2번지의 ‘하나’를 둘로 바꾸었습니다.

‘하나’ 가 ‘둘’로 바뀌었습니다.

// size() 메소드를 이용한 요소의 총 개수
		System.out.println("리스트의 크기 : " + lnkList.size());
	}
}

리스트의 크기는, 예상대로 3입니다.

Linkedlist의 장점과 단점을 아래 표로 요약할 수 있습니다.

다음 시간에는 linkedlist의 치명적인 단점을 어떻게 보완할지에 대해 알아보도록 하겠습니다.