[Collection Framework] 자바(Java) LinkedList(연결 리스트)의 사용법 & 예제 정리

코딩 테스트 문제풀이에 자주 사용하는 컬렉션 프레임워크 중 하나인 'Linked List'에 대해 정리해보려고 한다.

 

개념

LinkedList는 'List' 인터페이스를 구현한 클래스이며 알고리즘 풀이에 자주 사용되는 컬렉션 프레임워크의 일종이다.

각 노드는 '데이터'와 다음 노드를 가리키는 '포인터'로 구성되며, 마지막 노드의 포인터는 'Null'을 가리키게 된다.

이러한 구성 때문에 아래 그림과 같이 각각의 노드들이 연쇄적으로 이어지는 구조를 이루게 된다.

LinkedList의 자료구조 (출처 : https://server-engineer.tistory.com/130)

 

선언 & 생성

import java.util.List // List 라이브러리
import java.util.LinkedList; // LinkedList 라이브러리

List list = new LinkedList<Integer>(); // List 인터페이스를 Integer 자료형의 LinkedList 자료구조로 구현
LinkedList<String> strList = new LinkedList<String>(); // String 자료형의 LinkedList 자료구조 선언
LinkedList<Integer> intList = new LinkedList<Integer>(); // Integer 자료형의 LinkedList 자료구조 선언
LinkedList<Student> students = new LinkedList<Student>(); // Student 자료형의 LinkedList 자료구조 선언

기본적인 선언 방법은 위와 같이 LinkedList 타입의 자료구조에 new LinkedList<자료형>을 대입하는 방법을 통해서 선언하는 것이다.

주의할 점은 String 외의 int, char과 같은 자료형들은 Integer, Character와 같은 래퍼 클래스(Wrapper Class)로 바꿔서 선언해줘야만 한다.

또한, 배열에서 사용하는 것과 마찬가지로 Student와 같은 별도의 클래스를 만들어서 사용할 수도 있다.

LinkedList는 'List' 인터페이스를 구현한 컬렉션 클래스 중에 하나이기 때문에 List 타입의 자료구조에 new LinkedList<자료형>의 대입을 통해서 선언하는 것도 가능하다.

 

list.add(Object obj)

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<Integer>();

list.addFirst(5) // 값 5를 list의 맨 앞에 추가
list.addLast(7) // 값 7을 list의 맨 뒤에 추가
list.add(1) // 값 1을 list에 추가(파라미터가 하나만 주어졌을 때는 list의 맨 뒤에 값을 추가)
list.add(3, 2) // 값 3을 list의 1번째 인덱스에 추가(1번째를 포함한 인덱스 이후의 값들은 뒤로 한 칸씩 밀려남)

LinkedList는 하나로 이어져있는 연쇄 구조를 이루기 때문에 새로운 값을 삽입할 때 일반적인 배열과는 다른 방식으로 동작한다.

아래 그림과 같이 기존 노드의 포인터가 새롭게 추가되는 노드를 가리키거나 새로 추가되는 노드의 포인터가 기존 노드를 가리키는 방식으로 동작하게 된다.

또한, LinkedList의 중간 인덱스에 새로운 값을 추가하는 경우에는 기존의 연결 관계를 끊고 새롭게 추가되는 노드와의 연결을 통해서 값을 추가하게 된다.

 

list.remove() & list.clear()

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1); list.add(2); list.add(3); list.add(4); list.add(5);

list.removeFirst(); // 맨 앞의 값을 삭제
list.removeLast(); // 맨 뒤의 값을 삭제
list.remove(); // 맨 앞의 값을 삭제
list.remove(2); // 2번째 인덱스에 위치한 값을 삭제
list.clear(); // 모든 값을 삭제

LinkedList의 전반적인 구조와 값을 삽입하는 과정을 이해하였다면 값을 삭제하는 과정 또한 이해하기 어렵지 않다.

제거 대상 노드를 가리키는 포인터가 해당 노드가 가리키고 있던 노드를 가리키게 되면, 제거 대상 노드는 더이상 접근할 수 없으므로 해당 노드는 제거된다.

 

list.get(int index)

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1); list.add(2); list.add(3);

System.out.println(list.get(0)); // list의 0번째 값 1을 출력

위의 예시에서는 LinkedList에서 index번째 노드가 가리키는 값을 가져온다.

 

list.set(int index, Object obj)

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1); list.add(2); list.add(3);

list.set(0, 5); // list의 0번째 값을 5로 변경

System.out.println(list.get(0)); // 5
System.out.println(list.get(1)); // 2
System.out.println(list.get(2)); // 3

노드가 가리키는 값을 변경한다.

 

list.size() 

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1); list.add(2); list.add(3);

System.out.println(list.size()); // list에 값이 3개 저장되어 있으므로 3 출력

현재 LinkedList를 구성하는 노드의 개수를 반환한다.

 

list.contains() & list.indexOf() 

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(1); list.add(2); list.add(3) list.add(3);

System.out.println(list.contains(1)); // list의 값 중에 1이 있으므로 true 출력
System.out.println(list.contains(5)); // list의 값 중에 5가 없으므로 false 출력

System.out.println(list.indexOf(2)); // list에서 값 2가 위치하는 인덱스 1 출력
System.out.println(list.indexOf(3)); // list에서 값 3이 중복되므로 가장 앞에 오는 인덱스 2 출력
System.out.println(list.indexOf(4)); // list에서 값 4을 찾지 못했으므로 -1 출력

LinkedList.contains()는 단순히 찾고자 하는 값이 LinkedList에 존재하는지 판단하기 위해서 쓰인다. 따라서 값이 존재하면 'true'를 반환하며, 존재하지 않으면 'false'를 반환한다.

LinkedList.indexOf()는 찾고자 하는 값이 LinkedList에 존재하면 해당 데이터가 존재하는 인덱스를 반환한다. 만약에 존재하지 않으면 '-1'을 반환한다.