[JAVA] LinkedList 메소드 정리

세하·2025년 4월 23일

Java문법 linkedlist

JAVA

목록 보기

7/17

LinkedList

LinkedList는 ArrayList와 마찬가지로 List를 구현한 클래스이므로 ArrayList와 비슷한 메소드를 구현하고있다.

LinkedList 각각의 노드가 next와 prev 노드값을 내부적으로 가지고있어 삽입, 삭제가 용이하며 변경되는 노드만 다시 연결해주면 되어 노드 추가와 삭제시 O(1)으로 속도가 빠르다.

그러나 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 즉, 순차탐색이므로 조회시엔 O(n)으로 속도가 느리다.

사용자가 데이터를 넣은 순서대로 next 포인터를 통해 연결되어 있어 논리적 저장 순서는 유지되지만, ArrayList처럼 연속된 메모리 공간에 저장되지 않고 노드들은 메모리의 임의 위치에 있고 포인터로만 연결되기 때문에 물리적 저장 순서는 일치하지 않는다.)

결국 어느 한 위치에 삽입, 삭제를 하고자 할 때도 처음부터 search를 한 후에 삽입, 삭제를 수행하게 되므로 이 또한 결국 O(n)의 시간이 추가적으로 필요하게 된다.

조회 : O(n)
삽입, 삭제 : O(n)
그러나 예외로 리스트의 가장 끝 부분에 추가할때는 last라는 변수가 마지막 노드를 가리키고 있기 때문에 순차탐색 없이 바로 마지막에 연결이 가능함.

조회시엔 ArrayList를 사용하는것이 좋음!
https://velog.io/@seha01130/ArrayList-정리

기본 List 메소드 예시

선언

import java.util.LinkedList;

LinkedList<Integer> list1 = new LinkedList<>();
LinkedList<Integer> list2 = new LinkedList<>(list1); //다른 Collection값을 전달해서 해당 값으로 초기화
LinkedList<Integer> list3 = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5)); // Arrays.asList()로 한 번에 여러 개의 값을 입력하면서 초기화

요소 추가, 변경

LinkedList<String> animals = new LinkedList<>();

animals.add("dog");
animals.add("cat");
animals.add(0, "elephant");
animals.add("hamster");

animals.set(0, "rabbit");

System.out.println(animals);

-----결과-----
[rabbit, dog, cat, hamster]

add()를 호출하여 dog과 cat가 순서대로 추가된 후 elephant가 맨 앞에 추가되고, hamster는 다시 가장 뒤에 추가된다
순서 : elephant dog cat hamster
그 후 set()를 호출하여 가장 맨 앞에 있는 elephant을 rabbit으로 변경한다.
순서 : rabbit dog cat hamster

요소 삭제

LinkedList<String> animals = new LinkedList<>(Arrays.asList("rabbit", "dog", "cat", "hamster", "snake"));
String removedAnimal1 = animals.remove(0);
System.out.println("Removed animal is " + removedAnimal1);

animals.remove("cat");
System.out.println(animals);

String removedAnimal2 = animals.remove();
System.out.println("Removed animal is " + removedAnimal2);
System.out.println(animals);

animals.clear();
System.out.println(animals);

-----결과-----
Removed animal is rabbit
[dog, hamster, snake]
Removed animal is dog
[hamster, snake]
[]

remove(...)를 사용하여 원하는 인덱스를 넣거나, 원하는 값을 입력하여 삭제 가능
remove(index)나 remove()를 사용하면 삭제한 값을 리턴받을 수 있다.
remove()만 사용하면 맨 앞의 값을 삭제해줌.
clear()를 호출하여 리스트 안의 전체 값을 삭제.

LinkedList 전체 값 확인

LinkedList<String> animals = new LinkedList<>(Arrays.asList("rabbit", "dog", "cat", "hamster", "snake"));

// for-each문
for (String am : animals) {
	System.out.print(am + " ");
}
System.out.println();

// for문
for (int i = 0; i < animals.size(); i++) {
	System.out.print(animals.get(i) + " ");
}
System.out.println();

// iterator
Iterator<String> itr = animals.iterator();
while (itr.hasNext()) {
	System.out.print(itr.next() + " ");
}
System.out.println();

// listIterator
ListIterator<String> listItr = animals.listIterator(animals.size()); //끝에서 시작
while (listItr.hasPrevious()) {
	System.out.print(listItr.previous() + " ");
}
System.out.println();

-----결과-----
rabbit dog cat hamster snake 
rabbit dog cat hamster snake
rabbit dog cat hamster snake
snake hamster cat dog rabbit

Iterator는 순차탐색
ListIterator는 양방향탐색

listIterator(index)로 시작 위치 지정 가능
next(), previous() 모두 가능 (양방향)
요소 추가/삭제/수정 가능

값 존재 유무 확인

LinkedList<String> animals = new LinkedList<>(Arrays.asList("rabbit", "dog", "cat", "hamster", "snake"));

boolean contains = animals.contains("cat"); // true

int index = animals.indexOf("dog"); // 1

index = animals.indexOf("lion"); // -1

contains()를 호출하여 원하는 값이 있는지 여부를 true/false로 알 수 있음
indexOf()를 호출하여 해당 값이 존재하는지 (없으면 -1 리턴), 존재하면 해당 index위치를 리턴함.

전체 메소드 정리

기본 List 메서드 (List 인터페이스 계열)

add(E e) | 맨 뒤에 요소 추가
add(int index, E e) | 특정 위치에 요소 삽입
remove() | 맨 앞 요소 제거 (큐처럼)
remove(int index) | 특정 위치 요소 제거
remove(Object o) | 특정 값 요소 제거
get(int index) | 인덱스로 요소 조회
set(int index, E e) | 인덱스의 요소 수정
indexOf(Object o) | 첫 번째 해당 요소 인덱스
lastIndexOf(Object o) | 마지막 해당 요소 인덱스
size() | 요소 개수 반환
isEmpty() | 비어 있는지 확인
clear() | 전체 요소 제거
contains(Object o) | 특정 요소 포함 여부

양방향 큐(Deque) 관련 메서드 (Deque 인터페이스 계열)

addFirst(E e) | 맨 앞에 요소 추가
addLast(E e) | 맨 뒤에 요소 추가
offer(E e) 큐처럼 요소 추가 (add보다 예외 덜 남)
offerFirst(E e) | 맨 앞에 요소 추가 (실패 시 false 반환)
offerLast(E e) | 맨 뒤에 요소 추가 (실패 시 false 반환)
getFirst() | 맨 앞 요소 조회
getLast() | 맨 뒤 요소 조회
peek() 맨 앞 요소 조회 (큐처럼, 제거는 안 함)
peekFirst() | 맨 앞 요소 조회 (비어있으면 null)
peekLast() | 맨 뒤 요소 조회 (비어있으면 null)
removeFirst() | 맨 앞 요소 제거
removeLast() | 맨 뒤 요소 제거
poll() 큐처럼 맨 앞 제거하고 반환
pollFirst() | 맨 앞 요소 제거 후 반환 (비어있으면 null)
pollLast() | 맨 뒤 요소 제거 후 반환 (비어있으면 null)

add vs offer
add()는 용량 초과 시 예외 발생, offer()는 실패 시 false 반환 → offer가 안전

getFirst() vs peekFirst()
비어 있을 때 getFirst()는 예외, peekFirst()는 null 반환 → peek가 안전