방앗간

※ 연결리스트 테스트 - Listl 인터페이스를 구현한 LinkedList를 테스트하는 방법은 다음과 같다 public class Tester{ public static void main (String[] args){ static Listl List = new LinkedList (); int n = 10; // 연결 리스트 생성 for(int i = 0; i =0; i--) int x = list.removeFirst(); // removeLast도 가능 }

※ Peek 메소드 - peek 메소드는 하나의 요소를 살펴보기 위해 쓰는 메소드로 추가, 제거하는 것이 아닌 그 요소의 내용을 읽는 함수이다. peekFirst는 다음과 같이 구현이 가능한데 리스트가 비어있으면 NullPointerException 에러가 발생하기 때문에 따로 처리를 해주어야 한다. public E peekFirst(){ if(head==null) return null; return head.data; } 같은 방식으로 peekLast는 다음과 같이 임시 포인터를 활용해 시간 복잡도가 O(n)인 peekLast 함수를 만들 수 있다. public E peekLast(){ if (tail==null) return null; return tail.data;

※ find - Comparable 인터페이스를 사용하여 노드를 찾습니다. public boolean contains(E obj){ Node current = null; while(current != null){ if(((Comparableobj).compareTo(current.data)==null) return true; current = current.next; } return false; } ※ remove 1. Comparable 인터페이스를 사용해 제거하고 싶은 요소의 위치를 찾습니다. 2. 바로 앞 노드의 next 포인터가 다음 노드를 가리키게 만들어 가운데 노드를 제거하고 previous, current 2가지 포인터를 사용해 각각 바로 앞의 노드와 제거하고자 하는 노드를 가리킨다. 노드가..

※ removeLast 메소드 - 마지막 노드를 마지막에서 2번째 노드로 옮겨 연결리스트의 마지막 노드를 제거하고 단일 연결 리스트이므로 2번째 노드를 찾으려면 head에서부터 시작해야 한다. 임시 포인터 current와 previous를 활용해 마지막에서 2번째 노드를 찾을 수 있는데 current는 현재 위치를 가리키는 포인터고 previous는 이전 위치를 가리키는 포인터이다. current 포인터가 tail과 같을경우 previous 포인터는 마지막에서 2번쨰 노드를 가리키게 된다. 이 경우에도 특정 조건에서 에러가 발생하는데 그 예시는 바로 자료 구조가 비어있는 경우와 자료 구조에 단 하나의 요사만 들어있는 경우로 removeFirst와 동일하게 예외 처리를 해주면 해결이 된다. public E..

※ removeFirst 메소드 - 보통 head = head.next를 하면 head가 다음 노드를 가리키고 첫 번째 노드가 제거된다. 하지만 다음과 같은 경계 조건에서 에러가 발생하기 때문에 코드를 추가할 필요가 있다. 조건1. 자료 구조가 비어있는 경우 - head가 null을 가리키는 경우인데, head가 head.next를 가리키면 NullPointerException 에러가 발생하게 되는데 이 상황에서는 아무것도 하지않고 null을 반환하면 된다. 조건2. 자료 구조에 단 하나의 요소가 들어있는 경우 - head 포인터, tail 포인터 모두 null을 가리키게 해야 한다. 이를 코드로 구현하면 다음과 같다 public E removefirst() { //경계 조건1 if (head == nu..

※ addLast 메소드 - addLast 메소드에선 연결 리스트의 마지막을 가리키는 임시 포인터를 사용한다. 연결 리스트의 요소를 확인하기 위해 무조건 head에서 시작해야 하는데, 연결 리스트의 마지막까지 도달하는데 next를 너무 많이 사용해야 한다. 그리고 연결 리스트의 마지막 노드는 유일하게 next 포인터가 null을 가리키기 떄문에, 다음과 같이 addLast 메소드를 작성할 수 있다. public void addLast(E obj) { Node tmp = head; while(tmp.next != null) tmp = tmp.next tmp.next = node; } 경계조건 에서의 문제 - head가 비어있는 경우는 tmp가 null이 되고, tmp.next를 찾지 못하는 NullPoin..

※ addFirst 메소드 - 새로운 node를 연결 리스트 앞부분에 추가하기 위해 먼저 새로운 노드를 만들고 새로운 node의 next가 현재 head를 가리키도록 한 뒤 head 포인터가 다시 새로운 노드를 가리키도록 하면 된다. 위 과정을 코드로 작성하면 다음 예시와 같다. public void addFirst(E obj){ Node node = new Node(obj); node.next = head; head = node; } 이 예시는 새로운 요소를 추가하기 위해 뒷부분을 볼 필요가 없어 시간 복잡도가 1이 나온다.

※ 노드와 크기 public class LinkedList implements Listl{ //노드 정의 class Node{ E data; Node next; public Node(E obj){ data = obj; next = null; } } private Node head; //노드 개수를 세는 변수 private int currentSize; //기본 연결리스트 public LinkedList(){ head = null; currentsize = null; } } - 다음 예시는 연결 리스트의 내부 클래스에서 노드를 정의한 예시이다. 노드는 next 포인터와 data를 가진다. data의 자료형은 E이고 E는 정해지지 않은 자료형으로 이런 방식으로 구현한 연결 리스트를 사용하면 그때 지정하겠다는..

※ 연결 리스트 - 포인터를 사용해 여러 노드를 연결하는 자료 구조를 연결 리스트라고 한다. 연결 리스트의 기본 구성 요소는 노드인데 여기엔 두 가지 정보가 들어있다. 첫 번째는 인접한 노드를 가리키는 next라는 이름의 포인터, 두 번째는 우리가 노드에 넣는 데이터를 가리키는 포인터이다. 이러한 리스트는 head라는 이름의 포인터에서 시작하고 Head는 리스트의 첫 번째 노드를 의미합니다. 힙에서는 이 연결 리스트의 head만 알고있어 head.next 나 head.data 등으로 노드의 내용을 찾는다. 하지만 연결 리스트의 길이가 긴 경우는 계속 next를 붙이는데 한계가 있어 임시 포인터를 이용해 탐색하는 방법을 사용한다. ※ 배열과의 차이 - 배열도 순서대로 여러 데이터를 저장할 때 사용한다는 공..

※ 예외(Exception) // Exception 클래스 상속 public class FileFormatException extends Exception{ public File FormatException () { // super 호출 super(); } public FileFormatException (String s){ super(s); } } // 예외 상황이 발생하면 throw throw new FileFormatException("Your file is not well formatted") 위 코드와 같이 Exception 클래스를 상속받고 생성자를 만든 후, 생성자 안에서 super를 호출하면 예외 상황에 대한 클래스를 만들 수 있다. 이후 예외 상황이 발생했을 때 throw 사용하면, 예외..