Java LinkedList
자바 LinkedList: 개념 및 사용법
- *
LinkedList*는 자바에서 제공하는 데이터 구조 중 하나로, 연결 리스트(Linked List) 방식을 사용하여 데이터를 저장합니다.LinkedList는 리스트의 중간에 데이터를 삽입하거나 삭제할 때 효율적인 성능을 제공하는 자료 구조입니다.ArrayList와 달리 요소가 연속된 메모리 공간에 저장되지 않고, 각각의 요소가 다음 요소의 참조를 갖는 형태로 연결되어 있습니다.
자바에서 LinkedList는
.util 패키지에 포함되어 있으며, List 인터페이스와 Deque
인터페이스를 구현합니다. 이를 통해 LinkedList는 양방향 큐처럼 사용할 수 있으며, 스택 및 큐와 같은 자료 구조로도 활용될 수 있습니다.
1. LinkedList의 특징
- 동적 크기:
LinkedList는 동적으로 크기가 변경되며, 메모리가 부족하지 않다면 요소를 계속 추가할 수 있습니다. - 빠른 삽입과 삭제: 중간에 요소를 삽입하거나 삭제하는 작업이 효율적입니다. 삽입 및 삭제는 해당 노드와 이웃 노드의 참조만 변경하면 되기 때문에 빠릅니다.
- 순차적인 접근이 빠름: 첫 번째 요소에서부터 차례대로 요소에 접근하는 것이 빠르지만, 특정 인덱스에 바로 접근하는 것은 느립니다.
- 노드의 연결: 각각의 요소(노드)는 다음 노드의 주소를 가리키고 있어 연속적인 메모리 공간을 사용하지 않아도 됩니다.
2. LinkedList 선언 및 생성
LinkedList를 사용하려면 먼저 **
.util.LinkedList**를 임포트해야 합니다. LinkedList는 제네릭(Generic)을 사용하여 저장할 데이터의 타입을 지정할 수 있습니다.
선언 및 생성 예제
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// String 타입의 LinkedList 생성
LinkedList<String> fruits = new LinkedList<>();
// Integer 타입의 LinkedList 생성
LinkedList<Integer> numbers = new LinkedList<>();
}
}
위 예제에서는 String 타입과 Integer 타입의 LinkedList를 각각 생성했습니다.
**제네릭(Generic)**을 사용하여 리스트에 저장할 데이터의 타입을 지정할 수 있으며, 지정된 타입 이외의 데이터를 추가하려고 하면 컴파일 오류가 발생합니다.
3. LinkedList 주요 메서드
LinkedList는 다양한 메서드를 제공하여 데이터를 추가, 삭제, 검색, 수정하는 기능을 지원합니다. 주요 메서드는 다음과 같습니다.
3.1 add() - 요소 추가
add() 메서드는 LinkedList에 요소를 추가하는 데 사용됩니다. 인덱스를 지정하지 않으면 리스트의 끝에 요소가 추가됩니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
// 요소 추가
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 출력
System.out.println(fruits); // 출력: [Apple, Banana, Orange]
}
}
3.2 get() - 요소 가져오기
get() 메서드는 특정 인덱스에 있는 요소를 반환합니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 인덱스 1에 있는 요소 가져오기
String fruit = fruits.get(1);
System.out.println(fruit); // 출력: Banana
}
}
3.3 size() - 리스트 크기 확인
size() 메서드는 LinkedList에 저장된 요소의 개수를 반환합니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
// 리스트 크기 확인
System.out.println(fruits.size()); // 출력: 2
}
}
3.4 set() - 요소 수정
set() 메서드는 특정 인덱스에 있는 요소를 새로운 값으로 수정합니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
// 인덱스 1의 값을 수정
fruits.set(1, "Mango");
System.out.println(fruits); // 출력: [Apple, Mango]
}
}
3.5 remove() - 요소 삭제
remove() 메서드는 특정 인덱스를 사용하거나 특정 요소를 지정하여 LinkedList에서 삭제할 수 있습니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 인덱스 1의 요소 삭제
fruits.remove(1);
System.out.println(fruits); // 출력: [Apple, Orange]
// 특정 요소를 삭제
fruits.remove("Apple");
System.out.println(fruits); // 출력: [Orange]
}
}
3.6 contains() - 요소 포함 여부 확인
contains() 메서드는 특정 요소가 LinkedList에 포함되어 있는지 여부를 확인합니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
// 특정 요소 포함 여부 확인
System.out.println(fruits.contains("Apple")); // 출력: true
System.out.println(fruits.contains("Mango")); // 출력: false
}
}
3.7 isEmpty() - 리스트가 비어 있는지 확인
isEmpty() 메서드는 LinkedList가 비어 있는지 확인합니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
// 리스트가 비어 있는지 확인
System.out.println(fruits.isEmpty()); // 출력: true
fruits.add("Apple");
System.out.println(fruits.isEmpty()); // 출력: false
}
}
3.8 clear() - 모든 요소 삭제
clear() 메서드는 LinkedList에 저장된 모든 요소를 제거합니다.
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
// 모든 요소 삭제
fruits.clear();
System.out.println(fruits); // 출력: []
}
}
4. LinkedList와 큐(Queue) 및 스택(Stack)
LinkedList는 Deque 인터페이스를 구현하므로 스택(Stack) 또는
**큐(Queue)**처럼 사용할 수 있습니다. 즉, LinkedList를 사용해 FIFO(First-In, First-Out) 방식이나
LIFO(Last-In, First-Out) 방식의 자료 구조를 구현할 수 있습니다.
4.1 큐(Queue)로 사용
큐는 먼저 들어온 요소가 먼저 나가는 선입선출(FIFO) 자료 구조입니다.
큐로 사용 예제
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
// 요소 추가 (Enqueue)
queue.add("Alice");
queue.add("Bob");
queue.add("Charlie");
// 요소 제거 (Dequeue)
System.out.println(queue.remove()); // 출력: Alice
System.out.println(queue.remove()); // 출력: Bob
}
}
4.2 스택(Stack)으로 사용
스택은 마지막에 들어온 요소가 먼저 나가는 후입선출(LIFO) 자료 구조입니다.
스택으로 사용 예제
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> stack = new LinkedList<>();
// 요소 추가 (Push)
stack.push("Alice");
stack.push("Bob");
stack.push("Charlie");
// 요소 제거 (Pop)
System.out.println(stack.pop()); // 출력: Charlie
System.out.println(stack.pop()); // 출력: Bob
}
}
5. ArrayList와 LinkedList의 차이점
| 특징 | ArrayList | LinkedList | |----------------
- --|-----------------------------------------------|---------------------------------------------------| | 데이터 구조 | 동적 배열 | 이중 연결 리스트 | | 삽입/삭제 속도| 리스트의 중간에서 삽입 또는 삭제가 느림 | 리스트의 중간에서 삽입 또는 삭제가 빠름 | | 랜덤 접근 속도| 인덱스를 통한 빠른 접근 가능 | 특정 인덱스로 접근하는 데 시간이 더 걸림 | | 메모리 사용 | 배열의 크기 조절을 위해 추가 메모리 필요 | 노드에 대한 추가 메모리 사용 | | 사용 용도 | 빠른 데이터 조회가 필요할 때 | 빈번한 데이터 삽입/삭제가 필요할 때 |
6. 반복문을 사용한 LinkedList 순회
LinkedList는 반복문을 사용하여 요소를 순회할 수 있습니다. 일반적인 for문, 향상된
for문, **Iterator**를 사용할 수 있습니다.
향상된 for문을 사용한 순회
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// 향상된 for문을 사용하여 요소 출력
for (String fruit : fruits) {
System.out.println(fruit);
}
}
}
Iterator를 사용한 순회
import java.util.LinkedList;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
// Iterator를 사용하여 요소 반복
Iterator<String> iterator = fruits.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
요약
- *
LinkedList*는 연결 리스트를 사용한 자료 구조로, 중간에서 삽입 또는 삭제가 빠르고 유연한 데이터 구조입니다. - 주요 메서드로는
add(),get(),remove(),size(),set(),contains()등이 있으며, 리스트의 삽입, 삭제, 조회 등을 처리할 수 있습니다. - 큐(Queue) 및 스택(Stack) 자료 구조로도 사용할 수 있어 다양한 방식으로 활용할 수 있습니다.
- *
ArrayList와LinkedList*는 서로 다른 성능 특성을 가지므로, 사용 목적에 따라 선택할 수 있습니다. 빠른 조회가 필요한 경우ArrayList, 빈번한 삽입과 삭제가 필요한 경우LinkedList가 적합합니다.
LinkedList는 효율적인 삽입과 삭제 작업을 제공하며, 자바 컬렉션 프레임워크에서 다양한 작업에 유용하게 사용될 수 있는 자료 구조입니다.