Home > Algorithm > 2024 > πŸ“¦[DS,Algorithm] LinkedListλ₯Ό μ‚¬μš©ν•œ Deque.

πŸ“¦[DS,Algorithm] LinkedListλ₯Ό μ‚¬μš©ν•œ Deque.
DataStructure Algorithm

1️⃣ LinkedListλ₯Ό μ‚¬μš©ν•œ Deque.

β€˜LinkedListβ€˜ λŠ” β€˜Dequeβ€˜ μΈν„°νŽ˜μ΄μŠ€λ₯Ό κ΅¬ν˜„ν•œ 클래슀 쀑 ν•˜λ‚˜λ‘œ, μ–‘μͺ½ λμ—μ„œ μ‚½μž…κ³Ό μ‚­μ œκ°€ κ°€λŠ₯ν•œ 이쀑 μ—°κ²° 리슀트 기반의 자료 κ΅¬μ‘°μž…λ‹ˆλ‹€.

β€˜LinkedListβ€˜ λŠ” β€˜Dequeβ€˜ 뿐만 μ•„λ‹ˆλΌ β€˜Listβ€˜, β€˜Queueβ€˜ μΈν„°νŽ˜μ΄μŠ€λ„ κ΅¬ν˜„ν•˜μ—¬ λ‹€μ–‘ν•œ ν˜•νƒœλ‘œ μ‚¬μš©ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

2️⃣ μ£Όμš” νŠΉμ§•.

  • 이쀑 끝 큐 : μ–‘μͺ½ λμ—μ„œ μš”μ†Œλ₯Ό μΆ”κ°€ν•˜κ³  μ œκ±°ν•  수 μžˆμŠ΅λ‹ˆλ‹€.

  • 이쀑 μ—°κ²° 리슀트 : 각 λ…Έλ“œλŠ” 이전 λ…Έλ“œμ™€ λ‹€μŒ λ…Έλ“œλ₯Ό κ°€λ¦¬ν‚€λŠ” 두 개의 포인터λ₯Ό κ°€μ§‘λ‹ˆλ‹€.

  • 비동기적 : β€˜LinkedListβ€˜ λŠ” λΉ„λ™κΈ°μ μœΌλ‘œ λ™μž‘ν•˜λ―€λ‘œ λ™κΈ°ν™”λœ ν™˜κ²½μ—μ„œ μ•ˆμ „ν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

3️⃣ μ£Όμš” λ©”μ„œλ“œ.

μ‚½μž… μ—°μ‚°.

  • β€˜addFirst(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 μ•žμͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

  • β€˜addLast(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 λ’€μͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

  • β€˜offerFirst(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 μ•žμͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

  • β€˜offerLast(E e)’ : μ§€μ •λœ μš”μ†Œλ₯Ό 덱의 λ’€μͺ½μ— μΆ”κ°€ν•©λ‹ˆλ‹€.

μ‚­μ œ μ—°μ‚°.

  • β€˜removeFirst()’ : 덱의 μ•žμͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜removeLast()’ : 덱의 λ’€μͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜pollFirst()’ : 덱의 μ•žμͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜pollLast()’ : 덱의 λ’€μͺ½μ—μ„œ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

쑰회 μ—°μ‚°.

  • β€˜getFirst()’ : 덱의 μ•žμͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜getLast()’ : 덱의 λ’€μͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜peekFirst()’ : 덱의 μ•žμͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

  • β€˜peekLast()’ : 덱의 λ’€μͺ½μ— μžˆλŠ” μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.

μŠ€νƒ μ—°μ‚°.

  • β€˜push(E e)’ : μŠ€νƒμ˜ 맨 μœ„μ— μš”μ†Œλ₯Ό μΆ”κ°€ν•©λ‹ˆλ‹€.(FIFO, First In First Out)

  • β€˜pop()’ : μŠ€νƒμ˜ 맨 μœ„μ— μžˆλŠ” μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.(LIFO, Last In First Out)

4️⃣ μ‹œκ°„ λ³΅μž‘λ„

  • μ‚½μž…κ³Ό μ‚­μ œ μ—°μ‚° : β€˜addFirstβ€˜, β€˜addLastβ€˜, β€˜removeFirstβ€˜, β€˜removeLastβ€˜, β€˜offerFirstβ€˜, β€˜offerLastβ€˜, β€˜pollFirstβ€˜, β€˜pollLastβ€˜ λ“±μ˜ 연산은 O(1)μž…λ‹ˆλ‹€.
    • 이쀑 μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜κΈ° λ•Œλ¬Έμ— μ–‘μͺ½ λμ—μ„œμ˜ μ‚½μž…κ³Ό μ‚­μ œλŠ” μƒμˆ˜ μ‹œκ°„ 내에 μˆ˜ν–‰λ©λ‹ˆλ‹€.
  • 쑰회 μ—°μ‚° : β€˜getFirstβ€˜, β€˜getLastβ€˜, β€˜peekFirstβ€˜, β€˜peekLastβ€˜ λ“±μ˜ 연산은 O(1)μž…λ‹ˆλ‹€.

  • μž„μ˜ μ ‘κ·Ό μ—°μ‚°( **β€˜get(int index)β€˜, β€˜set(int index, E element)’ λ“±) :** 인덱슀λ₯Ό μ‚¬μš©ν•œ μ ‘κ·Ό 연산은 리슀트의 쀑간에 μžˆλŠ” μš”μ†Œλ₯Ό μ°ΎκΈ° μœ„ν•΄ 리슀트λ₯Ό μˆœνšŒν•΄μ•Ό ν•˜λ―€λ‘œ O(n) μ‹œκ°„μ΄ κ±Έλ¦½λ‹ˆλ‹€.

5️⃣ μ½”λ“œ μ˜ˆμ‹œ.

μ•„λž˜ μ½”λ“œλŠ” β€˜LinkedListβ€˜ λ₯Ό β€˜Dequeβ€˜ 둜 μ‚¬μš©ν•˜λŠ” μ˜ˆμ œμž…λ‹ˆλ‹€.

import java.util.Deque;
import java.util.LinkedList;

public class LinkedListDequeExample {

	public static void main(String[] args) {
		// LinkedList둜 Deque 생성
		Deque<Integer> deque = new LinkedList<>();

		// μš”μ†Œ μ‚½μž…
		deque.addFirst(1);
		deque.addLast(2);
		deque.offerFirst(0);
		deque.offerLast(3);

		// μš”μ†Œ 쑰회
		System.out.println("First element: " + deque.getFirst());
		System.out.println("Last element: " + deque.getLast());
		System.out.println("Peek first element: " + deque.peekFirst());
		System.out.println("Peek last element: " + deque.peekLast());

		// μš”μ†Œ μ‹μ œ
		System.out.println("Removed first element: " + deque.removeFirst());
		System.out.println("Removed last element: " + deque.removeLast());
		System.out.println("Poll first element: " + deque.pollFirst());
		System.out.println("Poll last element: " + deque.pollLast());

		// 덱의 크기와 λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€ 확인
		System.out.println("Deque size: " + deque.size());
		System.out.println("Is deque empty? " + deque.isEmpty());

		// μŠ€νƒ μ—°μ‚°.
		deque.push(4);
		System.out.println("Pushed element: " + deque.peekFirst());
		System.out.println("Popped element: " + deque.pop());
	}
}
/*
=== 좜λ ₯ ===

First element: 0
Last element: 3
Peek first element: 0
Peek last element: 3
Removed first element: 0
Removed last element: 3
Poll first element: 1
Poll last element: 2
Deque size: 0
Is deque empty? true
Pushed element: 4
Popped element: 4
*/

πŸ™‹β€β™‚οΈ μ„€λͺ….

    1. λ² μ—΄ μ΄ˆκΈ°ν™” : β€˜DEFAULT_CAPACITYβ€˜ 크기의 배열을 μ΄ˆκΈ°ν™”ν•˜κ³ , β€˜headβ€˜, β€˜tailβ€˜, β€˜sizeβ€˜ λ³€μˆ˜λ₯Ό μ΄ˆκΈ°ν™” ν•©λ‹ˆλ‹€.
    1. μ‚½μž… μ—°μ‚°( **β€˜addFirstβ€˜, β€˜addLastβ€˜) :** μš”μ†Œλ₯Ό 덱의 첫 번째 λ˜λŠ” λ§ˆμ§€λ§‰μ— μΆ”κ°€ν•©λ‹ˆλ‹€.
    1. μ‚­μ œ μ—°μ‚°( **β€˜removeFirstβ€˜, β€˜removeLastβ€˜) :** 첫 번째 μš”μ†Œμ™€ λ§ˆμ§€λ§‰ μš”μ†Œλ₯Ό 각각 μ œκ±°ν•©λ‹ˆλ‹€.
    1. 쑰회 μ—°μ‚°( **β€˜getFirstβ€˜, β€˜getLastβ€˜, β€˜peekFirstβ€˜, β€˜peekLastβ€˜) :** 첫 번째 μš”μ†Œμ™€ λ§ˆμ§€λ§‰ μš”μ†Œλ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
    1. 기타 λ©”μ„œλ“œ : β€˜sizeβ€˜ 와 β€˜isEmptyβ€˜ λ©”μ„œλ“œλŠ” 덱의 크기와 λΉ„μ–΄ μžˆλŠ”μ§€ μ—¬λΆ€λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
    1. μŠ€νƒ μ—°μ‚°( **β€˜pushβ€˜, β€˜popβ€˜) :** μŠ€νƒμ˜ 맨 μœ„μ— μš”μ†Œλ₯Ό μΆ”κ°€ν•˜κ³ , μŠ€νƒμ˜ 맨 μœ„μ— μžˆλŠ” μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  λ°˜ν™˜ν•©λ‹ˆλ‹€.

μœ„ μ˜ˆμ‹œ μ½”λ“œμ—μ„œλŠ” β€˜LinkedListβ€˜ λ₯Ό β€˜Dequeβ€˜ 둜 μ‚¬μš©ν•˜μ—¬ λ‹€μ–‘ν•œ 연산을 μˆ˜ν–‰ν•˜λŠ” 방법을 λ³΄μ—¬μ€λ‹ˆλ‹€.
β€˜LinkedListβ€˜ λŠ” 이쀑 μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜κΈ° λ•Œλ¬Έμ— μ–‘μͺ½ λμ—μ„œμ˜ μ‚½μž…κ³Ό μ‚­μ œκ°€ λΉ λ₯΄κ³  νš¨μœ¨μ μž…λ‹ˆλ‹€.