개발공부 블로그

*TIL 66에서 정리한 자료구조 강의 이어서 정리 데이터를 저장하기 위해 배열이 존재한다 전화번호를 키로 사용한다고 가정했을때, 값은 전화번호와 연관된 사람 key, phone, numbers 등이 있다 전화번호를 키로 쓰기에 너무 길다고 판단할 수 있다 -> 전화번호를 받는 해시함수를 구현 -> 전화번호를 세 숫자로 잘라서 합한다고 가정하고 키 값을 생성한다 생기는 문제점 다른 사람의 번호를 추가 할 때, 두 개의 키가 같은 배열안에 위치한다 -> 충돌이 발생 해시 충돌 서로 다른 값을 가진 키가 일치하는 경우를 말한다 배열에 두 키가 같은 공간에 들어갈 수 없기 때문에 충돌이 발생한다 folding : 긴 숫자를 작은 숫자로 분해한다 -> 작은 숫자들의 합을 사용할 수 있다 숫자가 무작위가 아니기 ..

연결리스트는 수용량이 정해져 있지 않고, 스택과 큐를 사용하기위해 만들 수 있다 리스트 내에 무언가를 찾고 싶을때의 시간복잡도 O(n)이다 -> 비효율적이다 리스트 내의 데이터를 조회할 때 유용한 데이터 구조를 사용해야 한다. Hash : 해시 여러 상황에서 데이터를 빠르게 추가하거나 제거하도록 한 데이터 구조이다 또한 데이터를 빠르게 찾을 수 있는 자료구조가 해시이다 키와 값을 가지고 있으며 키가 주어지면 바로 연관된 값을 찾을 수 있다 Hash 메서드 add() : 요소를 추가한다 remove() : 요소를 제거한다 lookup/find/contains : 어떠한 요소를 찾고자 할때 사용한다 change : 특정 요소를 수정하고 싶을 때 사용한다 엔트리를 불러오는 메서드 : all entries 모든..

원형 연결리스트 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..

연결리스트 맨 앞에 데이터를 추가하는 경우 리스트가 있고 연결리스트의 생성자를 호출할 때 가장 먼저 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..