List(리스트)

List

• 순서를 가지고 데이터를 저장하는 자료구조
• Arrary List, Linked List가 존재
  • Array List
    • 연속된 메모리에 저장하는 구조
  • LinkedList
    • 주소값을 가지고 비연속된 메모리에 저장하는 구조로 주소값을 통해 다음 값을 알 수 있음

Array List

• 특징
  • 고정된 저장 공간
  • 순차적인 데이터
• static array(정적 배열)
  • 선언 시에 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속적/순차적으로 저장하는 자료구조(static array)⇒ dynamic array 사용
  • ⇒ 매번 고정되어진 크기 때문에 해당 크기보다 크게 저장이 불가능함
  • random access
    • 배열 변수는 자신의 첫번째 주소값을 가리킴
    • 첫번째 주소값만 알고 있으면 어떤 주소든 접근 가능
    • array 특성인 연속된 메모리 할당 때문에 random access가 가능
  • 한번의 접근만으로 원하는 곳에 접근이 가능 해서 O(1)의 시간 복잡도를 가짐
• dynamic array(동적 배열)
  • 정적 배열과 다르게 동적배열은 사이즈를 늘릴 수 있음
  • static array 기반임
  • resizing 과정을 거쳐기존 배열의 2배 추가
  • ⇒ 이때 시간복잡도는 O(n)임
  • resizing 과정
    1. 기존 배열 보다 크게 배열을 생성
    2. 기존 배열을 옮겨 닮고 새로 추가할 값을 추가
    3. 기존 배열 삭제
• 시간복잡도

Static arrayDynamic array

access / update	$O(1)$	$O(1)$
insert_back	$O(1)$	amortized $O(1)$
delete_back	$O(1)$	$O(1)$
insert_at	$O(n)$	$O(n)$
delete_at	$O(n)$	$O(n)$서

• 선언과 초기화는 O(n)의 시간 복잡도를 가짐
• 정렬 안된 배열을 정렬하면 O(nlogn)이 걸림 ⇒ 외워야함

 

Linked List

• 특징
  • Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조
  • Node는 데이터 값과 next node의 주소값을 저장
  • 비연속적으로 저장되어짐
  • next node의 메모리 주소값을 가리킴으로써 논리적인 연속성을 갖게 됨
  • 물리적 비연속적, 논리적 연속적
  • 메모리 사용이 좀 더 자유롭지만 주소값을 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 큼

import java.util.*;

class BrowserHistory {
    public String homepage;
    public LinkedList<String> history;
    public int curPoint;


    public BrowserHistory(String homepage) {
        this.homepage = homepage;
        history = new LinkedList<>();
        history.add(homepage);
        curPoint = 0;
        
    }
    
    public void visit(String url) {
        curPoint++;

        if(curPoint == history.size()){
            history.add(url);
        } else {
            history.set(curPoint, url);
        }

        while(curPoint < history.size()-1){
            history.removeLast();
        }
        
    }
    
    public String back(int steps) {
        curPoint = curPoint-steps < 0 ? 0 : curPoint-steps;
        return history.get(curPoint);
        
    }
    
    public String forward(int steps) {
        curPoint = curPoint+steps > history.size()-1 ? history.size()-1 : curPoint+steps;
        return history.get(curPoint);
    }
}

 

출처 : https://www.inflearn.com/course/코딩테스트-입문-파이썬/

코딩테스트 [ ALL IN ONE ] - 인프런 | 강의

문제 : https://leetcode.com/problems/design-browser-history/description/