링크드리스트 학습
public class DoubleLinkedList<T> {
// 더블 링크드리스트(Doubly linked list)기본 구조
// 이중 연결이라고도 한다.
// 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
public Node<T> head = null;
public Node<T> tail = null;
public class Node<T>{
T data;
Node<T> prev =null;
Node<T> next =null;
public Node(T data){
this.data = data;
}
}
// 데이터값 삽입
public void addNode(T data){
if(this.head == null){
this.head = new Node<T>(data);
this.tail = this.head;
}else{
Node<T> node = this.head;
while(node.next != null){
node = node.next;
}
node.next = new Node<T>(data);
node.next.prev = node;
this.tail =node.next;
}
}
public void printAll(){
if(this.head != null){
Node<T> node = this.head;
System.out.println(node.data);
while(node.next != null){
node = node.next;
System.out.println(node.data);
}
}
}
// head 부터 특정 노드를 찾는 메서드 추가하기
public T searchFromHead(T isData){
if(this.head == null){
return null;
}else{
Node<T> node = this.head;
while(node != null){
if(node.data == isData){
return node.data;
}else{
node = node.next;
}
}
return null;
}
}
// tail 부터 특정 노드를 찾는 메서드 추가하기
public T searchFromTail(T isData){
if(this.head == null){
return null;
}else{
Node<T> node = this.tail;
while(node != null){
if(node.data == isData){
return node.data;
}else{
node = node.prev;
}
}
return null;
}
}
// 데이터를 임의 노드 앞에 노드를 추가하는 메서드 추가하기
public boolean insertToFront(T existeData, T addData){
if(this.head == null){
this.head = new Node<T> (addData);
this.tail = this.head;
return true;
}else if(this.head.data == existeData){
Node<T> newHead = new Node<T>(addData);
newHead.next = this.head;
this.head = newHead;
return true;
}else{
Node<T> node = this.head;
while(node != null){
if(node.data == existeData){ //노드의 데이터를 찾으면
Node<T> nodePrev =node.prev; //노드에 prev 노드를 nodePrev에 저장
//nodePrev <-> nodePrev.next <->node
//연결 작업
nodePrev.next = new Node<T>(addData); //새로운 노드를 nodePrev.next로 저장
nodePrev.next.next = node; //기존 노드를 nodePrev.next.next로 저장
nodePrev.next.prev= nodePrev; //새로운 노드의 다음노드의 prev에 연결 (자기랑)
node.prev =nodePrev.next; //node.prev의 다음노드를 기존 노드의 prev로 연결
return true;
}else{ //못찾으면 다음으로 넘어감
node =node.next;
}
}
return false;
}
}
public static void main(String[] args) {
DoubleLinkedList<Integer> MyLinkedList = new DoubleLinkedList<Integer>();
// 테스트 : 데이터 삽입
MyLinkedList.addNode(1);
MyLinkedList.addNode(2);
MyLinkedList.addNode(3);
MyLinkedList.addNode(4);
MyLinkedList.addNode(5);
MyLinkedList.printAll();
System.out.println("##################################");
// 테스트 : head 부터 특정 노드를 찾는 메서드 추가하기
System.out.println(MyLinkedList.searchFromHead(1));
// 테스트 : tail 부터 특정 노드를 찾는 메서드 추가하기
System.out.println(MyLinkedList.searchFromTail(1));
System.out.println("##################################");
// 테스트 : 데이터 사이에 삽입
MyLinkedList.insertToFront(3, 2);
MyLinkedList.printAll();
System.out.println("##################################");
MyLinkedList.insertToFront(6, 2);
MyLinkedList.insertToFront(1, 0);
MyLinkedList.printAll();
System.out.println("##################################");
MyLinkedList.addNode(6);
MyLinkedList.printAll();
System.out.println("##################################");
}
}
해쉬 테이블 학습 (계속)
import javax.print.attribute.HashAttributeSet;
public class MyHash {
// 해쉬 테이블
// 키(key)에 데이터(value)를 매핑할 수 있는 데이터 구조
// 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산
// Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라진다.
// 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원
// 해쉬 함수 (Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수(키를 넣으면 값을 반환)
// 해쉬 (Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(Hash Address) : 해싱함수를 통해 리턴된 고정된 길이의 값
// 해쉬 함수는 사용자 정의함수이다. 사용자가 원하는 기능으로 만든다.
// 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
// 슬롯(Slot) : 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간
// hash table 클래스 만들기
public Slot[] hashTable;
public MyHash(Integer size){
this.hashTable = new Slot[size];
}
public class Slot{
String value;
Slot(String value){
this.value = value;
}
}
// 해쉬 함수 만들기
//Key가 문자열일 때, 문자열의 앞 글자를 숫자로 변환해서, Division 기법을 사용하여 , Key에 대한 주소(인덱스 번호) 계산
//Division 기법 : 가장 간단한 해쉬 함수 중 하나로 , 나누기를 통해, 나머지 값을 사용하는 기법
public int hashFunc(String key){
return (int)(key.charAt(0)) % this.hashTable.length;
}
// 객체 배열
// 객체 베열 선언시 , 각 배열의 아이템은 각 객체를 참조할 수 있는 주소를 담을 수 있는 공간만 할당
// -각 아이템 생성시, 별도로 각 객체를 생성해줘야 한다.
// -즉, 객체 배열 선언시, 각 생성할 객체를 가리킬 주소만 저장할 공간을 배열로 만드는 것
//저장 성공유무 반환 및 값을 저장하는 메서드
public boolean savaData(String key, String value){
Integer address =this.hashFunc(key);
if(this.hashTable[address]!= null ){
this.hashTable[address].value = value;
}else{
this.hashTable[address] = new Slot(value);
}
return true;
}
//특정 key에 대한 데이터를 가져오는 메서드
public String getData(String key){
Integer address =this.hashFunc(key);
if(this.hashTable[address] != null){
return this.hashTable[address].value;
}else{
return null;
}
}
public static void main(String[] args) {
//테스트 : 값 저장후 , 출력
MyHash mainObject = new MyHash(20);
mainObject.savaData("DaveLee","01022223333");
mainObject.savaData("fun-coding","01033334444");
System.out.println(mainObject.getData("fun-coding"));
}
}