[Java] List Interface: LinkedList Class

💡LinkedList Class

---

• Collection(I) > List(I) > ArrayList(C), LinkdedList(C)

ArrayList vs LinkedList

ArrayList와 LinkedList는 겉으로 보기에 사용법은 같지만, 내부 구조가 완전히 다르다.

이때 내부 구조가 다르다는 말은 사용 목적이 다르다는 의미이다.

 

LinkedList Class 종류

1. LinkedList

일방통행 구조이므로 앞으로만 갈 수 있다.

첫 번째 값을 확인할 수 있으면서 두 번째 값의 주소도 알아낼 수 있다는 특징이 있다.

2. Double LinkedList

양방향 통행이 가능한 구조로, 앞 뒤로 갈 수 있다.

3. Double Circle LinkedList

양방향 통행이 가능하며, 처음과 끝을 연결한 구조이다.

시작 방에서 끝 방에 갈 수 있고, 끝 방에서 시작 방에 갈 수 있는 원형 구조이다.

자바의 링크드리스트는 Double Circle LinkedList 방식을 채택했다.

 

ArrayList vs LinkedList

ArrayList는 모든 컬렉션 중에서 요소에 접근하는 속도가 가장 빠르지만, 요소 삽입/삭제(Shift 발생)에 대한 비용이 많이 든다.

그리고 LinkedList는 요소에 접근하는 속도가 상대적으로 느리지만, 요소 삽입/삭제(Shift 발생)에 대한 비용이 거의 없다는 특징이 있다.

결론적으로 내가 이 배열을 만들어서 무슨 일을 할것인지에 따라서 효율이 달라진다. 따라서 내부구조에 따라 결정하도록 한다.

소스코드를 통해 차이를 확인해보도록 하자.

 

LinkedList 배열 선언

ArrayList<Integer> list1 = new ArrayList<Integer>();
LinkedList<Integer> list2 = new LinkedList<Integer>();

long begin = 0, end = 0;

 

순차적으로 데이터 추가하기, Append

System.out.println("[순차적으로 데이터 추가하기, Append]");

// ArrayList
begin = System.currentTimeMillis();
for(int i=0; i<1000000; i++) {
    list1.add(i); // 배열 끝에 추가
}
end = System.currentTimeMillis();

System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

// LinkedList
begin = System.currentTimeMillis();
for(int i=0; i<1000000; i++) {
    list2.add(i); // 배열 끝에 추가
}
end = System.currentTimeMillis();

System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);

/*
[순차적으로 데이터 추가하기, Append]
ArrayList 작업 시간: 22ms
LinkedList 작업 시간: 172ms
*/

데이터 추가를 1,000,000번 시행한 결과 ArrayList는 약 0.22초, LinkedList는 약 1.72초 정도 걸렸다. 이는 컴퓨터 사양에 따라서 달라진다.
특수한 경우가 아닌 이상, 이 정도 차이는 거의 차이가 없다고 결론을 내릴 수 있는 정도이다.

 

순차적으로 데이터 삭제하기, Delete (Shift 발생 X)

System.out.println("[순차적으로 데이터 삭제하기, Delete]");

// ArrayList
begin = System.currentTimeMillis();
for(int i=list1.size()-1; i>=0; i--) {
    list1.remove(i); // 끝 > 시작
}
end = System.currentTimeMillis();

System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

// LinkedList
begin = System.currentTimeMillis();
for(int i=list2.size()-1; i>=0; i--) {
    list2.remove(i); // 끝 > 시작
}
end = System.currentTimeMillis();

System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);
/*
[순차적으로 데이터 삭제하기, Delete]
ArrayList 작업 시간: 5ms
LinkedList 작업 시간: 18ms
*/

데이터 삭제를 1,000,000번 시행한 결과, ArrayList는 약 0.07초, LinkedList는 약 0.18초 정도 걸렸다.
순차적으로 삭제하는 것은 ArrayList와 LinkedList 둘 다 빨랐다.

 

중간에 데이터 삽입하기, Insert

System.out.println("[중간에 데이터 삽입하기, Insert]");

// ArrayList
begin = System.currentTimeMillis();
for(int i=0; i<10000; i++) {
    list1.add(0, i); // 삽입하기
}
end = System.currentTimeMillis();

System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

// LinkedList
begin = System.currentTimeMillis();
for(int i=0; i<10000; i++) {
    list2.add(0, i); // 삽입하기
}
end = System.currentTimeMillis();

System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);
/*
[중간에 데이터 삽입하기, Insert]
ArrayList 작업 시간: 1,823ms
LinkedList 작업 시간: 1ms
*/

 

Shift 비용이 발생하는 경우에는 어떤 차이가 있는지를 확인해 보자.
데이터 삽입을 10,000번 시행한 결과, ArrayList는 약 1.823초, LinkedList는 약 0.01초 정도 걸렸다.
배열을 만들 때 사이에 끼워 넣는 일이 주 업무일 경우 LinkedList를 사용하는 것이 좋다.

 

중간에 데이터 삭제하기, Delete (Shift 발생 O)

System.out.println("[중간에 데이터 삭제하기, Delete]");

// ArrayList
begin = System.currentTimeMillis();
for(int i=0; i<10000; i++) {
    list1.remove(0); // 삭제하기
}
end = System.currentTimeMillis();

System.out.printf("ArrayList 작업 시간: %,dms\n", end - begin);

// LinkedList
begin = System.currentTimeMillis();
for(int i=0; i<10000; i++) {
    list2.remove(0); // 삭제하기
}
end = System.currentTimeMillis();

System.out.printf("LinkedList 작업 시간: %,dms\n", end - begin);
/*
[중간에 데이터 삭제하기, Delete]
ArrayList 작업 시간: 1,293ms
LinkedList 작업 시간: 1ms
*/

데이터 삭제를 10,000번 시행한 결과, ArrayList는 약 1.293초, LinkedList는 약 0.01초 정도 걸렸다.
이처럼 데이터 삽입이나 삭제에 Shift가 발생하는 경우, LinkedList를 사용하는 게 좋다.