[TIL] 큐&연결리스트

 

Queue: 선입선출 방식으로 데이터 처리하는 자료 구조.

1)큐생성

Queue<int> queue = Queue<int>();

2)큐에 값 추가

queue.add(1);

3) 큐 다루기

queue.removeFirst(); //앞에서 삭제
queue.first; //앞쪽 값 반환
queue.last; //뒤쪽 값 반환
queue.isEmpty //큐가 비어있는지 확인
queue.length //큐의 길이 확인

4)예시

* 문제
클래스 RecentCounter를 구현하세요.
이 클래스는 주어진 시간 범위 내에서 호출 수를 기록하고 반환합니다.

RecentCounter()는 RecentCounter 객체를 초기화합니다.
int ping(int t)는 t (밀리초 단위, 비내림차순) 시점에서 호출되었음을 기록하고, [t - 3000, t] 범위 내에서 발생한 모든 호출 수를 반환합니다.

* 조건
1. 1 <= t <= 10^9
2. ping은 최대 10,000번 호출될 수 있습니다.

* 예시
1. 입력:
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // [1], 반환값: 1
recentCounter.ping(100);   // [1, 100], 반환값: 2
recentCounter.ping(3001);  // [1, 100, 3001], 반환값: 3
recentCounter.ping(3002);  // [100, 3001, 3002], 반환값: 3
설명: 3000밀리초 내의 호출만 유지하며, 각 호출 범위 내의 호출 수를 반환합니다.

>>답안

import 'dart:collection';
class RecentCounter {
    Queue<int> queue = Queue<int>(); //필드 선언및 초기화

    RecentCounter(); //생성자
  
    int ping(int t) {
        queue.add(t);
        while(queue.isNotEmpty && queue.first<t-3000){
            queue.removeFirst();
        }
        return queue.length;
    }
}

 

 

---

연결리스트: 각 데이터가 자신과 다음 데이터를 가리키는 포인터(혹은 참조)를 가지고 있는 형태로 이루어진 자료 구조

노드: 데이터 연결하는 기본 단위
헤드: 연결리스트의 첫번째 노드를 가리키는 참조
테일:연결리스트의 마지막 노드 가리키는 참조


data: 노드에 저장될 실제 값
next: 다음 노드를 가리키는 참조. 초기 설정은 null
isEmpty(): 연결리스트가 비어있는지 확인하는 메서드

1) 노드 생성

class Node {
  int data;  // 노드에 저장할 데이터
  Node? next; // 다음 노드를 가리키는 포인터 (null을 허용)

  Node(this.data); // 생성자에서 data를 초기화
}

2) 연결리스트 생성

class LinkedList {
  Node? head; // 첫 번째 노드를 가리키는 헤드 포인터

  // 연결리스트가 비어있는지 확인
  bool isEmpty() {
    return head == null;
  }

3) 연결리스트에 데이터 추가

// 연결리스트 끝에 노드를 추가
  void append(int data) {
    Node newNode = Node(data);

    if (head == null) {
      // 리스트가 비어있으면 새로운 노드를 첫 번째 노드로 설정
      head = newNode;
    } else {
      Node current = head!;
      // 마지막 노드를 찾기 위해 리스트를 순차적으로 탐색
      while (current.next != null) {
        current = current.next!;
      }
      // 마지막 노드의 next 포인터를 새 노드로 설정
      current.next = newNode;
    }
  }

4) 연결리스트에서 데이터 삭제

  // 특정 데이터를 가진 노드를 삭제
  void delete(int data) {
    if (isEmpty()) return;

    if (head!.data == data) {
      // 첫 번째 노드가 삭제할 노드인 경우
      head = head!.next;
      return;
    }

    Node current = head!;
    Node? prev;

    while (current != null && current.data != data) {
      prev = current;
      current = current.next!;
    }

    if (current == null) return; // 데이터가 리스트에 없으면 아무 것도 하지 않음

    prev?.next = current.next; // prev 노드의 next를 삭제된 노드의 다음 노드로 설정
  }
}

5) 예시

* 문제
단일 연결 리스트의 헤드가 주어졌을 때, 리스트를 역순으로 뒤집으세요.

* 조건
1. 연결 리스트의 노드 개수는 0≤n≤5000 입니다.
2. 각 노드는 -5000 <= Node.val <= 5000의 정수 값을 가집니다.

* 예시
예시 1
	입력: head = [1,2,3,4,5]
	출력: [5,4,3,2,1]
	설명: 리스트를 역순으로 뒤집으면 [5,4,3,2,1]이 됩니다.

>>답안

class Solution {
  ListNode? reverseList(ListNode? head) {
    ListNode? prev = null;
    ListNode? current = head;

    while(current!=null){
        ListNode? temp = current.next;
        current.next = prev;
        prev = current;
        current= temp;

    }
    return prev;
    
  }
}

코드 해설

	예시 head:[1, 2, 3, 4]; 

        temp: 2 current: 1 prev: null / current.next=null prev:1 current:2 
        
        prev: 1 -> null
	current: 2 -> 3 -> 4 -> null

        
        temp:3 current:2 prev:1 / current.next:1 prev:2 current:3 
        
        prev: 2 -> 1 -> null
	current: 3 -> 4 -> null
        
        
        temp:4 current:3 prev:2/ current.next:2 prev:3 current:4 

	prev: 3 -> 2 -> 1 -> null
	current: 4 -> null
        
        temp:null current:4 prev:3/ current.next:3 prev:4 current: null 
        
        prev: 4 -> 3 -> 2 -> 1 -> null
	current: null
        
        -> current==null -> while 루프 종료

아직도 헷갈림