◀ PREV [1] NEXT ▶ Double Linked List • 더블 링크드리스트의 경우앞의 노드를 가리키는 prev 부분이 추가되엇다 insert와 remove 연산의 달라진 부분을 위주로 기억해두자public class MyDoubleLinkedList { private int size = 0; private Node firstNode = null; private Node lastNode = null; //노드 생성자에 앞의 노드를 가르키는 prev가 추가되었다 public static class Node { E item; Node prev; Node next; Node(Node prev, E element, Node next) { this.prev = prev; .. 2024. 5. 19. ArrayList • ArrayList 원소를 추가할때 배열에 남은 공간이 없으면?크기를 일정 배수로 늘린 배열 새로운 배열을 만들어 기존 배열의 원소를 옮긴다(자바에서 ArrayList는 1.5배, Vector는 2배 증가시킨다)중간 원소 삽입/삭제 연산은 기존 배열과 동일 == 느리다랜덤 액세스는 O(1)번 만에 가능하다 구현 코드import java.util.Arrays;public class MyArrayList { private static final int DEFAULT_CAPACITY = 10; private int size = 0; private Object[] data; //생성할떄 크기를 지정받으면 해당 크기만큼, 아니면 기본 크기인 10으로 생성한다 public MyArray.. 2024. 5. 18. Single Linked List • Single LinkedList node, next로 만 이루어진 구조 원소마다 node에 값을 가지고 다음 원소를 가리키는 link를 통해서 연결한다firstNode = null, lastNode = null로 초기화하고 시작한다순차적으로 접근할때 Iterator를 사용해 효율적으로 관리가 가능하다 addLast 연산 O(1)size가 0이면 firstNode를 newNode로그게 아니면 기존 lastNode.next를 newNode로 바꾸고 lastNode를 newNode로 변경 addFirst 연산 O(1)size가 0이면 lastNode를 newNode로그게 아니면 firstNode를 newNode로 하고 firstNode.next를 기존 firstNode로 get 연산 O(N)특정 위치에.. 2024. 5. 18. 리스트와 배열의 차이, 리스트 인터페이스 배열 : 동일한 타입의 원소를 선형적으로 관리하는 정적 데이터 구조 get - O(1)add 맨뒤에 추가 - O(1)insert 중간에 추가 - 넣으려는 인덱스부터 한칸씩 밀고 추가, o (N)remove - 삭제한 후 삭제한 인덱스 뒤를 한칸씩 당겨주느라 o (N) List - 동일한 타입의 원소를 선형적으로 관리하는 동적 데이터 구조크기 가변적, List 인터페이스 구현체에 따라 특성이 다르다 구현체 3개ArrayList - 인덱스를 통한 원소 접근 빠름, 삽입/삭제 느림LinkedList - 헤드부터 하나씩 타고 이동하기에 인덱스를 통한 접근 느림, 삽입 삭제는한 노드에서 자르고 포인터만 이어주면 되서 빠르다Vector - ArrayList와 비슷하고 thread - safe 해서 멀티 쓰레드 환경.. 2024. 5. 14. iterator, Listiterator List 컬렉션 클래스에서만 Listiterator를 사용 가능하다 LinkedList l = new LinkedList(); 로 이중연결리스트를 만들고 나서 ListIterator it = l.listIterator();를 선언해서 위의 Linkedlist를 순회하는 Listiterator를 사용할 수 있다..hasNext(), .hasPrevious(), .hasNext() - 앞이나 뒤에 요소가 있는지 확인 .next(), .previous() - 이동하면서 값을 반환 remove - 현재 it 위치에 있는 요소를 제거, add(E) - 현재 it 위치에 E를 추가 2023. 8. 27. LinkedList(이중 연결 리스트) https://www.codetree.ai/missions/6/problems/integer-command-processing-8?&utm_source=clipboard&utm_medium=text LinkedList l = new LinkedList(); 형태로 이중연결리스트 사용 addFirst(E) - 맨 앞에 데이터 E를 추가 addLast(E) - 맨 뒤에 데이터 E를 추가 pollFirst() - 맨 앞에 있는 데이터를 반환하면서 리스트에서 삭제 pollLast() - 맨 뒤에 있는 데이터를 반환하며서 리스트에서 삭제 size() - 현재 list에 들어있는 데이터의 수 isEmpty() - 현재 list가 비어있다면 true, 아니라면 false peekFirst() - list의 맨 앞에 .. 2023. 8. 27. 동적 배열 https://www.codetree.ai/missions/6/problems/process-numeric-commands-5?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai ArrayList name = new ArrayList(); 형태로 동적 배열을 선언 add, remove, get, size 등의 인덱스가 있다 ArrayList 등 컬렉션에 정의되어 있는 자료구조 순회 - iterator 반복자 ArrayList v = new ArrayList(); Iterator itera.. 2023. 8. 27. 이전 1 다음