linkedlist
-
Array vs LinkedListCS 지식/자료구조 2021. 1. 14. 15:45
Array vs LinkedList Array 논리 저장 순서랑 물리 저장 순서가 일치함 인덱스로 원소에 접근이 가능하기 때문에, O(1)로 엑세스 가능 삭제 or 삽입은 해당 원소에 접근하여 작업을 완료한 뒤(O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 맨 뒤에 요소를 추가하는 것은 O(1)이지만, 원래 존재하던 요소의 앞쪽에 삽입한다면 뒤에 있는 요소들의 인덱스를 +1씩 해줘야함 삭제의 경우도 뒤에 있는 요소들을 한칸씩 땡겨줘야함 (인덱스 -1) 위의 두 경우 모두 O(n)의 작업이 추가적으로 필요하다 LinkedList 논리 저장 순서와 물리 저장 순서가 일치하지 않음 논리 저장에는 실제 저장되어있는 요소의 주소 값이 들어있다. 각 원소들은 자신의 다음 원소..
-
BOJ) 에디터알고리즘/백준 2020. 7. 7. 20:09
에디터 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 www.acmicpc.net 풀이 총 3번을 제출했고, 마지막 한번만 맞았다. 처음에 푼 방법은, ArrayList에 char를 집어넣고 커서를 ArrayList의 size로 시작해서 LDBP를 구현했다. 풀면서 무조건 시간초과가 뜰거라고 생각했고, 9%에서 시간초과가 떴다. 그래서, 위의 방법과 커서는 똑같이 가져가고 ArrayList대신 StringBuffer로 문자열을 제거, 추가했다. 몰랐는데, StringBuffer에도 index에 값을 넣는 input 이라는 메소드가 존..