본문 바로가기

루프 발견 2.8 문제 - 루프 발견 순환 연결리스트가 주어졌을때, 순환되는 부분의 첫째 노드를 반환 하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는 변질된 방식 의 연결리스트를 의미한다. 입력: A > B > C > D >E> C (앞에 나온 C와 같음) // 입력 0 > 1 > 2 > 3> 4> 5> 6> 7> 8> 9> 10 > 3 출력 : C // 출력 3 문제 해결 방법 1. 연결리스트에서 순환 구조의 유무 검사 -탐색 속도가 다른 2개의 포인터를 이용. (RUNNER 기법) -SLOW: P만큼 나아갈때 1칸 -FAST: 2P만큼 나아간다 2칸 -이용해서 만나면 순환구조가 있다고 볼 수 있다. -루프가 아닌부분의 크기를 K 라고..
Doubly linked list(이중 연결 리스트) 직접 구현 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859package DoublyLinkedList; public class DoublyMain { public static void main(String[] args) { DoublyLinkedList numbers = new DoublyLinkedList(); numbers.addFirst(30);//맨 앞에 추가 numbers.addFirst(20); numbers.addFirst(10); System.out.println(numbers); System.out.println(numbers.removeLast());..
Linked list 와 Doubly linked list 의 개념과 차이점 1. Linked list 란 Array list의 경우 리스트의 엘리먼트가 배열의 엘리먼트인 반면에 linked list의 엘리먼트는 노드 객체를 사용 한다. 그래서 엘리먼트(노드 객체)와 엘리먼트(노드 객체)를 연결(link),레퍼런스를 통해서 리스트를 구현 한 것을 의미한다. Linked list 에서는 이 연결이 중요하다! 2. 단방향 Linked list 의 구조 - 각 노드는 다음 노드를 가리킨다 Node객체 안에 변수들을 봐보자 1) Data field : 저장되는 실제 값을 가리킨다 - 노드의 값(보통 value라는 변수 사용) 2) Link field : 다음 노드의 참조값, 주소값(보통 next라는 변수 사용)을 가리킨다. 이렇게 링크 필드로 노드와 노드를 연결시키는 방법을 사용 3) ..
ArrayList 직접 구현 ArrayList를 직접 구현해보았다. 코드 설명은 주석을 참고 바란다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667package Arraylist; public class ArrayListMain { public static void main(String[] args) { ArrayList numbers = new ArrayList(); numbers.add(10);//마지막 추가 numbers.add(20); numbers.add(30); numbers.add(40); numbers.add(1,15);//첫번째에 추가 nu..
Java의 ArrayList 사용법 1. ArrayList Java에서 ArrayList는 가장 많이 사용되는 데이터 스트럭쳐일 것이다. Java의 콜렉션 프레임워크 라이브러리안에 ArrayList를 기본적으로 내장하고 있다. ArrayList는 List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는특징을 갖는다. ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다. 2. ArrayList의 생성자와 메소드 https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html 3. ArrayList의 기본적인 예제 코드 1234567public class ArrayList extends Abst..
ArrayList(어레이 리스트) 1. 어레이 리스트(ArrayList) 리스트를 만들때 내부적으로 배열을 사용한다. 리스트라는 완제품안에 배열이라는 부품을 사용하는것이다. 이 배열안에 데이터를 저장하는것이다. 2. 장점 데이터에 접근하는 것이 빠르다. 배열의 인덱스를 이용해서 메모리 상의 주소를 정확하게 참조하 기 때문에 어디든지 한 번에 참조가 가능하며 특정 인덱스를 상수 시간에 접근한다! 3. 단점 배열의 길이가 초기에 결정되어야 한다. 데이터의 추가와 삭제가 느리다. 삭제 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다. 왜냐하면 데이터를 리스트의 처음이나 중간에 추가할려면 이후의 데이터들이 한칸씩 물러나야 한 다. 삭제도 빈자리가 생기면 빈자리를 채우기 위해서 순차적으로 한칸씩 땡겨야 한다. - 추가 - 삭제
배열과 리스트2 1. 배열(array)과 리스트의 성질 1) 배열의 가장 큰 특징은 인덱스를 중요시 한다는 점이다. 즉 인덱스를 값의 식별자로서 이용해 데이터를 조회를 한다는점이다. 하지만 인덱스를 이용 해 데이터를 가져오려면 데이터에 대한 인덱스의 값이 고정 되어야 한다. 그리고 어떤 엘리먼 트가 삭제되면 삭제된 상태를 빈 공간으로 남겨둬야 한다. 그래서 메모리의 낭비를 초래하고 배열에 데이터가 있는지를 체크하는 로직이 필요하다. 2) 리스트는 저장된 순서를 중요하게 여긴다. 리스트도 내부적으로 인덱스를 가질 수는 있지만 식별자로서의 인덱스를 중요시하기보다, 빈 틈없는 데이터의 적재라는 점을 취한다. 즉 "데이터의 다음 데이터는 무엇이다" 라는 저장된 순서를 중요하게 여기며, 데이터를 나란히(하나의 열로) 저장한다. ..
배열과 리스트1 1. 배열이란? 여러 연관된 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 data structure이다. 모든 언어에서 배열을 지원하고 많은 자료구조에서 배열을 부품적으로 이용하기 때문에 가장 기본적인 자료구조이면서 중요하다고 할 수 있다. 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있다. 배열의 구성요소는 값, 인덱스, 엘리먼트가 있다. 엘리먼트는 값과 인덱스를 합친것을 말한다 2. 배열의 반복 순회 예제 student 라는 배열의 변수를 한 학급의 반으로 보고 , 그 반이라는 배열에서 학생은 하나의 엘리먼 트로 표현할 수 있다. 학생의 이름은 배열의 값, 학생의 인덱스는 학번으로 기능할 수 있다. 배열에는 여러 정보가 저장되어 있다. 이러한 다수의 정보를 처리하기 위한 방법은 반복이고 ..