개발공부 블로그

원형 연결리스트 next포인터가 다음 노드를 가리키고 마지막 노드가 이미 살펴본 노드를 가리켜 리스트의 연결 형태가 원의 모양이 된다 원형 연결리스트임을 구분하는 법 1. data 한 개를 기록하고 하나씩 돌아가면서 다시 나타나는지 확인 -> 중복된 data가 있다면 쓸 수 없는 방식이다 2. head를 다시 찾을 때까지 살펴본다 3. 메모리 주소를 비교해본다 ->이 중 두번째 방법을 사용하면 좋다 head에서 임시 포인터 t를 선언하고 요소 한 개씩 넘어간다 멈추는 경우 임시 포인터 t = null; t == head || t.next == head 이 방법의 시간 복잡도 : O(n) 시간 복잡도는 tail포인터로 줄일 수 있다 if(tail.next == head) -> O(1) 원형으로 연결되어있지..

Doubly Linked Lists 이중 연결 리스트 단일 연결리스트의 단점 : tail 포인터가 있더라도 removeLast를 하기위한 시간 복잡도가 O(n)이다 -> 무조건 첫 번째 요소부터 세야한다 연결리스트 : next, data 값을 갖고있다 이중 연결리스트 : next, previous, data의 값을 가지고 있다 모든 노드에 previous와 next가 있다 tail 값 반환 E tmp = tail.data; tail.previous.next = null; tail = tail.previous; return tail; 이중 연결 리스트의 단점은 previous 포인터가 추가되기 때문에 노드를 추가하는 과정이 더 복잡해진다

peek 메서드 peek 메소드는 하나의 요소를 살펴보기 위해 쓰는 메소드로, 추가, 제거하는 것이 아니라 그 요소의 내용을 읽는 함수이다 removeFirst와 addFist를 하면 코드가 길어진다 -> head.data를 반환하는 peekFirst를 사용한다 코드 public E peekFirst() { if(head == null) return null; return head.data; } public E peekLast() { if(tail == null) return null; return tail.data } ** while(tmp.next != null) //마지막 요소에서 멈추는 반복문 -> peekFirst에 사용 //while(tmp != null) 마지막 노드를 지나치는 반복문 com..

removeLast 메서드 리스트 끝으로 도달함을 확인하는 코드이다 current == tail current.next = null //NullPointerException 발생할 수 있음 리스트가 비어있으면 null을 반환 removeLast는 removeFirst와 방식이 같다 **removeFirst : 리스트가 비어있거나 요소가 한개만 있는 상황 등에도 잘 실행된다 -> 코드를 그대로 사용 removeLast 코드 구현 public E removeLast() { if(head == null) return null; if(head == tail) return removeFirst(); //요소가 하나인 리스트 -> 여기서 끝 //리스트의 요소 살펴보기 Node current = head.previo..

한줄 요약 : 패키지 이름 java로 짓지 마세요 그런 사람이 여기 있었습니다 예외처리가 헷갈려서 실습하던 중 어김없이 오류가 발생했다 검색해보니 환경변수 등록을 안했거나, 자바 컴파일 버전과 자바의 버전이 안 맞아서 발생한다고 했는데 cmd 창에서 java - version javac - version (컴파일 버전) 을 검색해봐도 같은 버전이라고 나오는 것이다. 어떻게 해결할 수 있는지 고민하던 중 오류코드의 이 부분이 눈에 들어왔다 누가봐도 답이 여기있었는데 메세지만 보고 당황해서 구글링을 하고있었던 것이다. 세팅하면서 오류를 다 겪었다고 생각했는데 느슨해진 실습환경에 긴장감을 주는 경험이었다 + 왜 안되는 건지 생각해봤다 실습 코드를 짤 때 클래스 이름을 "Exception"이라고 짓는바람에 메인..

추상 자료형(abstract data type, adt) 추상적으로 정의된 자료형이다 추상 : 세부적이고 복잡한 것을 생략 대표적인 것, 중요한것만을 나타낸다 -자료구조를 기술하는 가장 대표적인 방법 중 하나 정보은닉 >중요한 정보만을 나타내고 중요하지 않은 것은 숨김 인터페이스(겉) 내부 구현 로직 자료구조를 사용할 수 있는 인터페이스(interface) 정의, 자료구조의 연산(operation)들의 정의 자료형 (data type) 자료 + 연산 =명령 예) 정수 자료형(int) 자료(data)-1,2,3,4 명령-더하기 빼기 곱하기 추상 자료형 MyPosition x좌표 y좌표의 위치를 나타내는 정수(자료) 명령 이름 입력(input) 출력(output) 설명 변경 modify() 1.위치자료 :p..

연결리스트 맨 앞에 데이터를 추가하는 경우 리스트가 있고 연결리스트의 생성자를 호출할 때 가장 먼저 head를 null로 지정한다 이를 증가시킬 것인지 감소시킬 것인지 고려해야 한다 새로운 요소를 추가할 떄 data와 next를 가지고 있는 노드 클래스를 만든다 비어있는 연결리스트의 head를 가지고와서 새로 생성된 노드를 가리키도록 만든다 또 다른 노드 B를 추가할 때는 head의 값을 옮기기만 한다면 연결이 사라진 노드 A는 삭제된다 이를 방지하기 위해 새로운 노드를 추가할 때는, 새로운 노드를 기존 노드 A를 가리키게 하고 head를 새로운 노드 B를 가리키게 해야 데이터를 잃지 않고 추가할 수 있다 -> 맨 앞에 요소를 추가하면서 연결리스트의 크기를 늘렸다 새로운 요소를 추가하기 위해 뒷 부분을 ..

LinkedList 연결리스트 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조를 연결 리스트라고 한다 여러 개의 포인터를 사용해서 힙에 있는 여러 공간을 가리킨다 연결리스트에 데이터를 저장할 수 있는 변수를 만들고 모든 내용을 담아서 잘 작동하게 만드는 것은 어렵다 객체는 공간이 할당 되어있기 때문에 값에 비해 공간이 넓거나, 공간이 부족한 경우가 생긴다 연결리스트는 순차적인 데이터나 많은 양의 데이터가 있을때 특히 자주 사용된다 많은 양의 데이터를 적은 양의 메모리를 사용해서 저장할 수 있다 *기본적인 연결리스트의 내용 연결리스트 -> 노드를 사용 노드에는 두가지 정보가 있음 next라는 포인터와 할당된 데이터가 기본 구성 요소이다 이런 노드가 같은 방식으로 다량 만들어져있다 //data에는 정..

매개변수화 타입(Parameterized Types) -특정 종류의 공간에 넣을 내용을 정의할 수 있게 한다 자료구조에서는 컨테이너를 분리해야 한다 = 컨테이너에 들어가는 내용이 분리되어야 한다 매개변수화 타입을 이용하면 컨테이너를 정의할 수 있다 MyContainer라는 객체를 정의했을때 어떤 종류의 내용이 들어갈지 정한다 Monkey객체를 넣으면 Monkey만 넣을 수 있는 컨테이너가 생성된다 이 컨테이너를 재사용할 수 있다 Mycontainer = new Mycontainer(); 컨테이너에 우리가 사용할 것들을 넣는다 -> 링크드 리스트, 이진트리, 큐, 스택 등에 사용가능 이 내용을 실제 구현 코드와 분리한다 //분리 후 자료구조를 이용해서 구현 + 실제 데이터와도 내용을 분리한다 자료구조에 들..

generic programming 제네릭 프로그래밍은 다양한 자료형의 객체에 대해 작성한 코드를 재사용한다는 객체 지향 기법이다 제네릭 프로그래밍이 없었다면 int를 String, Person 등 문자열, 원하는 객체로 바꿔야 했을 것이다 제네릭 프로그래밍의 목표는 1가지의 코드만 작성해서 이를 다른 자료형에 대해 재사용할 수 있게 만드는 것이다 정렬 알고리즘을 ss라고 가정했을 때 public class ss { public int[] superSort(int[] args) { ...sort... return array; } } 정수가 아닌 문자열에도 이 정렬을 적용하려면 어떻게 해야 할까? -> 제네릭 클래스를 이용하여 형변환한다 Person 객체도 똑같은 방식으로 추가해준다 public class..