[Java] LinkedList 그게 뭔데? 개념 & 사용법

hansung's·2024년 3월 21일

🤔 LinkedList란?

LinkedList는 Java Collection Framework에서 List 인터페이스를 구현한 클래스로, 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조 입니다.
또한, Deque 인터페이스 역시 구현하고 있어, 덱 또는 큐와 같이 사용할 수 있습니다.

LinkedList에 대해 더 설명하자면,

LinkedList는 ArrayList와 다르게 노드(Node)라는 객체로 구성되어 있는데, 노드에는 데이터를 저장하는 부분과 다음 노드에 대한 주소 포인터로 이루어져 있고, 노드 간 포인터를 서로 가리키며 연결된 구조입니다.

그래서 이름부터 리스트가 서로 연결되었다는, 연결 리스트로 불리는 것입니다.

JDK11 기준, LinkedList 클래스 안 Node 클래스의 구조입니다.
여기서 보다시피, item은 data를 의미하고, 해당 item에 대한 이전 포인터(prev), 다음 포인터(next)가 존재하는 것을 볼 수 있습니다.

그림으로 이를 나타내자면, 아래와 같을 수 있다.(※ 이중 연결 리스트의 모습)

이렇듯, 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전 노드와 연결을 담당한다.

😎 LinkedList 종류

singly linked list(단일 연결 리스트)

단일 연결 리스트는, 다음 노드의 포인터를 가리키는 next 필드만 존재한다.
next 포인터를 이용해 다음 Node로 접근할 수 있지만 이전 요소로 접근해야 할때는 단점이 존재한다.

만약, Linked List에 데이터가 100개가 존재하는데, 여기서 100번째 node에 접근하고자 하면 node를 100번 움직여야 하는 단점이 존재한다.

class Node<E> {
 	E item;
 	Node<E> next;
}

// class로 표기한다면 다음과 같은 필드 구조를 가질 것이다.

doubly linked list(이중 연결 리스트)

위에서 잠깐 보여줬던 그림으로, 단일 연결 리스트의 단점을 보완한 구조가
바로 이중 연결 리스트이다.

이중 연결 리스트는 단일 연결 리스트에서 prev 필드가 추가된 것으로, 해당 필드를 통해 이전 Node의 주소값을 참조할 수 있는 것이다.
이로써, 이중 연결 리스트는 next or prev 필드를 통해 리스트를 순차적으로 혹은 역순으로 접근할 수 있게 된다.

그래서 Java에서는 doubly linked list 형태로 LinkedList 클래스를 구현하였다.

doubly circular linked list(이중 원형 연결 리스트)

이중 연결 리스트에서 접근성이 더 개선된 이중 원형 연결 리스트가 존재하는데, 이는 첫 번째 노드와 마지막 노드의 주소 포인터를 연결하여, 마치 원형처럼 움직여서 원형 연결 리스트라고 불립니다.

🙄 LinkedList의 시간복잡도는??

LinkedList에서 중간에 데이터를 삽입 / 삭제시 시간복잡도는 O(N)으로,
먼저 중간에 삽입하고자 혹은 삭제하고자 하는 인덱스를 찾기 위해 검색하기 때문에 O(N)의 시간복잡도를 가집니다.

대신, ArrayList와 같이 삽입, 삭제 후 인덱스를 밀거나 당겨오는 작업이 존재하지 않고, 포인터 주소만 바꿔주면 되기 때문에 검색 이후로는 O(1)의 시간복잡도를 가집니다.

그럼, 추가는?
추가는 간단하게 tail노드(맨 마지막에 위치하는 노드) 뒤에 추가하는 것이기 때문에 O(1)의 시간복잡도를 가집니다.

😢 LinkedList 요약 정리 및 구조

설명이 조금 매끄럽지 못해 이를 간단하게 요약 정리한다면,

LinkedList 개념

LinkedList란, 노드가 다음 혹은 이전 주소 포인터를 가리키며 연결되는
선형 자료구조이다.

LinkedList 구조

연결 리스트의 구조는 다음과 같은데,
첫 번째 노드를 head 마지막 노드를 tail라 부른다.

LinkedList 시간 복잡도

중간에 삽입 / 삭제시 해당 위치까지 검색하며 움직어야 하기 때문에 O(N)의 시간복잡도를 가진다.

하지만, 위치를 찾으며 ArrayList와 달리 인덱스를 밀어주거나 끌어주는 행동을 할 필요 없어, O(1)의 시간 복잡도를 가진다.

데이터 추가와 같은 경우, tail노드를 찾아 뒤에 노드를 추가하면 되기 때문에 O(1)의 시간복잡도를 가진다.

👍 linkedList 사용법

LinkedList 클래스는 List 인터페이스를 구현한 것으로 ArrayList클래스가 사용하는 메서드와 유사하다.

또한, LinkedList는 Deque 인터페이스 역시 구현하고 있기 때문에 stack, Queue와 같은 자료구조로도 사용할 수 있어 해당 메서드까지 사용할 수 있다.

👩 linkedList 선언

import java.util.LinkedList;

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

👨 linkedList 노드 추가

import java.util.LinkedList;

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

linkedList.add("box2");
linkedList.addFirst("box1");
linkedList.addLast("box4");

linkedList.add(2, "box3");

Type	Method	설명
boolean	add(E e)	요소를 리스트 끝에(tail) 추가하는데 성공시 true, 실패시 false 반환
void	addFirst(E e)	리스트의 시작 부분(head)에 요소를 삽입
void	addLast(E e)	리스트의 끝 부분(tail)에 요소를 삽입
void	add(int idx, E e)	지정된 인덱스에 요소를 삽입

노드 추가를 그림으로 나타내면 다음과 같다.

🧑 linkedList 노드 삭제

import java.util.LinkedList;

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

linkedList.add("box2");
linkedList.addFirst("box1");
linkedList.addLast("box4");

linkedList.add(2, "box3");

linkedList.remove();		
linkedList.removeFirst();
linkedList.removeLast();

Type	Method	설명
Element	removeFirst()	첫 번째 요소(head)를 삭제하고 이를 반환합니다.
Element	removeLast()	마지막 요소(tail)를 삭제하고 이를 반환합니다.
Element	remove(int idx)	지정된 위치에 있는 요소를 삭제하고 이를 반환합니다.
Element	remove()	첫 번째 요소(head)를 삭제하고 이를 반환합니다.
void	clear()	모든 요소를 삭제합니다.

👧 linkedList 데이터 검색

import java.util.LinkedList;

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

linkedList.add("box2");
linkedList.addFirst("box1");
linkedList.addLast("box4");

linkedList.add(2, "box3");

linkedList.contains("box5");  	// false		
linkedList.indexOf("box2");		// 1
linkedList.lastIndexOf("box5");	// -1

Type	Method	설명
boolean	contains(Obj o)	리스트에 요소가 존재한다면 true, 아니면 false 반환
int	indexOf(Obj o)	리스트에서 요소가 처음 등장하는 인덱스를 반환, 만약 존재하지 않으면 -1 반환
int	lastIndexOf(Obj o)	리스트에서 요소가 마지막에 등장하는 인덱스를 반환, 만약 존재하지 않으면 -1 반환

👦 linkdList 데이터 얻기

import java.util.LinkedList;

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

linkedList.add("box2");
linkedList.addFirst("box1");
linkedList.addLast("box4");

linkedList.add(2, "box3");

linkedList.get(1);  		// box2		
linkedList.getFirst();  	// box1	
linkedList.getLast();  		// box4

Type	Method	설명
Element	get(int idx)	리스트에 지정된 위치의 요소를 반환
Element	getFirst()	리스트의 첫 번째(헤드) 요소를 반환
Element	getLast()	리스트의 마지막(테일) 요소를 반환

🧒 linkedList 데이터 변경

import java.util.LinkedList;

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

linkedList.add("box2");
linkedList.addFirst("box1");
linkedList.addLast("box4");

linkedList.add(2, "box3");

linkedList.set(1, "box5");