[Java/자바] LinkedList 클래스 사용법

기본적인 형태의 배열 ( array )는 구조가 간단하여 사용하기가 쉽고, 데이터를 읽어오는데 걸리는 시간이 가장 빠르다는 장점을 가지고 있습니다.

하지만 아래와 같은 단점도 가지고 있습니다.

Array ( 배열 ) 의 단점

1. 크기를 변경할 수 없다.
크기를 변경할 수 없기 때문에 새로운 배열을 생성해서 데이터를 복사해야한다.

2. 메모리 낭비
실행속도를 향상시키기 위해선 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.

3. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야한다.

 

LinkedList는 이러한 단점을 보완하기 위해 나오게 되었습니다.

---

LinkedList

배열은 모든 데이터가 연속적으로 존재하지만, 링크드리스트는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있습니다.

class Node {
	Node next; // 다음 요소의 주소를 저장
    	Object obj; // 데이터를 저장
}

 

 

링크드리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있습니다.

 

링크드 리스트 선언

import java.util.List;
import java.util.LinkedList;

List<타입> list1 = new LinkedList<>();
List<타입> list2 = new LinkedList<>(list1); // 주어진 컬렉션을 포함하는 LinkedList 객체 생성

 

 

링크드 리스트에서의 데이터 삭제

 

삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 됩니다.

단 하나의 참조만 변경하면 삭제가 이뤄지는 것입니다.

배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 처리속도가 매우 빠릅니다.

 

링크드 리스트에서의 데이터 추가

데이터를 추가할 때는, 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해줍니다.

그리고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠릅니다.

 

---

Doubly Linked List ( 이중 연결 리스트 )

 

링크드 리스트는 이동방향이 단방향으로, 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵습니다.

그래서 이 단점을 보완하고자 더블 링크드 리스트가 나오게 되었습니다.

class Node {
	Node next; // 다음 요소의 주소를 저장
    	Node previous; // 이전 요소의 주소를 저장
    	Object obj; // 데이터를 저장
}

 

더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가해 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외는 링크드 리스트와 같습니다.

더블 링크드 리스트는 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 더 많이 사용됩니다.

 

---

LikedList 메서드

 

메서드	반환 타입	설 명
add(Object o)	boolean	지정된 객체(o)를 LikedList 끝에 추가
add(int i, Object element)	void	지정된 위치(i)에 객체(element)를 추가
addAll(Collection c)	boolean	주어진 컬렉션에 포함된 모든 요소를 LikedList 의 끝에 추가.
addAll(int i, Collection c)	boolean	지정된 위치(i)에 주어진 컬렉션에 포함된 모든 요소를 추가
clear()	void	LikedList의 모든 요소 삭제
contains(Object o)	boolean	지정된 객체가 LikedList에 포함되어있는지 확인
containsAll(Collection c)	boolean	지정된 컬렉션의 모든 요소가 포함되어있는지 확인
get(int i)	Object	지정된 위치(i)의 객체를 반환
indexOf(Object o)	int	지정된 객체가 저장된 위치(앞에서 부터 몇번째) 반환
isEmpty()	boolean	LikedList가 비었는지 확인
iterator()	lterator	lterator를 반환
lastIndexOf(Object o)	int	지정된 객체의 위치(i)를 반환( 끝부터 역순 )
listlterator()	Listlterator	Listlterator를 반환
listlterator(int i)	Listlterator	지정된 위치에서부터 시작하는 Listlterator를 반환
remove(int i)	Object	지정된 위치(i)의 객체를 LikedList에서 제거
remove(Object o)	boolean	지정된 객체를 LikedList에서 제거
removeAll(Collection c)	boolean	지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
retainAll(Collection c)	boolean	지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
set(int i, Object element)	Object	지정된 위치(i)의 객체를 주어진 객체로 바꿈
size()	int	LikedList에 저장된 객체의 수를 반환
subList(int start, int end)	List	LikedList의 일부를 List로 반환
toArray()	Object[]	LikedList의 저장된 객체를 배열로 변환
toArray(Object [])	Object[]	LikedList에 저장된 객체를 주어진 배열에 저장하여 반환
element()	Object	LikedList의 첫 번째 요소 반환
offer(Object o)	boolean	지정된 객체(o)를 LikedList의 끝에 추가
peek()	Object	LikedList의 첫 번재 요소를 반환
poll()	Object	LikedList의 첫 번째 요소를 반환하고 LikedList에서 제거된다.
remove()	Object	LikedList의 첫 번째 요소 제거
addfirst(Object o)	void	LikedList의 맨 앞에 객체(o)를 추가
addLast(Object o)	void	LikedList의 맨 끝에 객체(o)를 추가
descendinglterator()	lterator	역순으로 조회하기 위한 Descendinglterator를 반환
getFirst()	Object	LikedList의 첫 번째 요소를 반환
getLast()	Object	LikedList의 마지막 요소를 반환
offerFirst(Object o)	boolean	LikedList의 맨 앞에 객체(o)를 추가.
offerLast(Object o)	boolean	LikedList의 맨 끝에 객체(o)를 추가
peekFirst()	Object	LikedList의 첫 번재 요소를 반환
peekLast()	Object	LikedList의 마지막 요소를 반환
pollFirst()	Object	LikedList의 첫 번째 요소를 반환하면서 제거
pollLast()	Object	LikedList의 마지막 요소를 반환하면서 제거
pop()	Object	removeFirst()와 같다.
push(Object o)	void	addFirst()와 같다.
removeFirst()	Object	LikedList의 첫 번째 요소를 제거
removeLast()	Object	LikedList의 마지막 요소를 제거
removeFirstOccurrence(Object o)	boolean	LikedList에서 첫 번째로 일치하는 객체를 제거
removeLastOccurrence(Object o)	boolean	LikedList에서 마지막으로 일치하는 객체를 제거

 

---

ArrayList와 LinkedList 비교

 

삭제, 추가 비교

import java.util.*; 

public class ArrayListLinkedListTest { 
      public static void main(String args[]) { 
            // 추가할 데이터의 개수를 고려하여 충분히 잡아야한다.
            ArrayList al = new ArrayList(2000000);
            LinkedList ll = new LinkedList(); 

            System.out.println("= 순차적으로 추가하기 ="); 
            System.out.println("ArrayList :"+add1(al)); 
            System.out.println("LinkedList :"+add1(ll)); 
            System.out.println(); 
            System.out.println("= 중간에 추가하기 ="); 
            System.out.println("ArrayList :"+add2(al)); 
            System.out.println("LinkedList :"+add2(ll)); 
            System.out.println(); 
            System.out.println("= 중간에서 삭제하기 ="); 
            System.out.println("ArrayList :"+remove2(al)); 
            System.out.println("LinkedList :"+remove2(ll)); 
            System.out.println(); 
            System.out.println("= 순차적으로 삭제하기 ="); 
            System.out.println("ArrayList :"+remove1(al)); 
            System.out.println("LinkedList :"+remove1(ll)); 
      } 

      public static long add1(List list) { 
            long start = System.currentTimeMillis(); 
            for(int i=0; i<1000000;i++) list.add(i+""); 
            long end = System.currentTimeMillis(); 
            return end - start; 
      } 

      public static long add2(List list) { 
            long start = System.currentTimeMillis(); 
            for(int i=0; i<10000;i++) list.add(500, "X"); 
            long end = System.currentTimeMillis(); 
            return end - start; 
      } 

      public static long remove1(List list) { 
            long start = System.currentTimeMillis(); 
            for(int i=list.size()-1; i >= 0;i--) list.remove(i); 
            long end = System.currentTimeMillis(); 
            return end - start; 
      } 

      public static long remove2(List list) { 
            long start = System.currentTimeMillis(); 
            for(int i=0; i<10000;i++) list.remove(i); 
            long end = System.currentTimeMillis(); 
            return end - start; 
      } 
}

출력 결과

위 출력 결과를 정리하면 다음과 같습니다.

순차적으로 추가, 삭제하는 경우 속도 비교 = ArrayList > LinkedList
중간에 데이터를 추가, 삭제하는 경우 속도 비교 = LikedList > ArrayList

 

읽기 (접근 시간) 비교

import java.util.*; 

public class ArrayListLinkedListTest2 { 
      public static void main(String args[]) { 
            ArrayList  al = new ArrayList(1000000); 
            LinkedList ll = new LinkedList(); 
            add(al);
            add(ll);

            System.out.println("= 접근시간 테스트 ="); 
            System.out.println("ArrayList :"+access(al)); 
            System.out.println("LinkedList :"+access(ll)); 
	  }

      public static void add(List list) { 
            for(int i=0; i<100000;i++) list.add(i+""); 
      } 

      public static long access(List list) { 
            long start = System.currentTimeMillis(); 

            for(int i=0; i<10000;i++) list.get(i); 

            long end = System.currentTimeMillis(); 

            return end - start; 
      } 
}

출력 결과

 

비교 결론

컬렉션	읽기(접근 시간)	추가 / 삭제	비 고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠르다. 비효율적인 메모리 사용.
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어진다.

• ArrayList는 많은 데이터에 대해 추가/삭제에는 불리하고, 읽기(참조)에는 유리
• LinkedList는 많은 데이터에 대해 추가/삭제는 유리하고, 읽기(참조)에는 불리

 

 

두 클래스의 장점을 이용해 아래 처럼 두 클래스를 조합해 사용할 수 있습니다.

처음에 작업하기 전에 데이터를 저장할 때는 ArrayList를 사용하다가, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 더 좋은 효율을 얻을 수 있습니다.

ArrayList array = new ArrayList(100000);
for(int i = 0; i < 100000; i++) array.add(i + "");

LinkedList link = new LinkedList(array);
for(int i = 0; i < 1000; i++) link.add(500 + "X");

 

---

참고자료
자바의 정석3