과제 2. LinkedList를 구현하세요.
- LinkedList에 대해 공부하세요.
- 정수를 저장하는 ListNode 클래스를 구현하세요.
- ListNode add(ListNode head, ListNode nodeToAdd, int position)를 구현하세요.
- ListNode remove(ListNode head, int positionToRemove)를 구현하세요.
- boolean contains(ListNode head, ListNode nodeTocheck)를 구현하세요.
과제 3. Stack을 구현하세요.
- int 배열을 사용해서 정수를 저장하는 Stack을 구현하세요.
- void push(int data)를 구현하세요.
- int pop()을 구현하세요.
과제 4. 앞서 만든 ListNode를 사용해서 Stack을 구현하세요.
- ListNode head를 가지고 있는 ListNodeStack 클래스를 구현하세요.
- void push(int data)를 구현하세요.
- int pop()을 구현하세요.
과제 5. Queue를 구현하세요.
- 배열을 사용해서 한번
- ListNode를 사용해서 한번.
1.LinkedList 란?
LinkedList는 ArrayList와 같이 여러가지 같은 타입의 오브젝트들을 모아 놓은 클래스이다. LinkedList는 ArrayList와 함께 List Interface를 구현하고 있기때문에 서로같은 메서드들(add , remove 등등 . .)을 포함하고 있다.
그러나 , ArrayList 와 LinkedList는 같은 방법으로 사용될 수는 있지만. 그 둘은 굉장히 다르게 만들어졌다 .
ArrayList 작동방식
ArrayList는 기본 배열을 구조를 가지고 있다 . 어떤 개체가 추가 될때 , 그 개체는 배열에 배치된다 . 배열의 크기가 충분하지 않은 경우 새로운 더큰 배열이 만들어지고 이전의 배열을 대체하며 , 이전 배열은 사라진다. 각 요소는 인덱스를 가지고 있기 때문에 한번에 참조가 가능해 데이터의 검색에 유리한 구현체이다
LinkedList 작동방식
LinkedList는 아이템을 "containers"에 배치한다 . 리스트는 첫 번째 컨테이너에 대한 링크가 있고 각 컨테이너에는 각각의 하나의 컨테이너에서 다음 컨테이너로 링크로 연결되 있다. 리스트에 요소를 추가하면 그 요소에 새컨테이너가 배치되고 해당 컨테이너가 목록의 다른 컨테이너 중 하나에 연결된다. 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다 , ArrayList와 다르게 데이터 추가 ,삭제시 불필요한 데이터의 복사가 없어 데이터의 추가 ,삭제에 유리하지만, 데이터 검색시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리하다.
위는 LinkedList와 ArrayList의 아이템 삭제시 메모리 구조를 비교한 그림이다 .
ArrayList는 새로운 임시 배열을 만들고 3번아이템을 제외한 아이템을 새로운 배열에 복사 한다 .
LinkedList는 3번 아이템이 제거 되고 2번과 4번 container가 link로 연결된다.
LinkedNode 구현
LinkedList와 관련메서드 addFirst, addLast, add, removeFirst , removeLast , remove , get , getSize ,toString을
구현해 보았다 .
package create_data_structure;
public class LinkedList {
//첫 번째 노드
private Node head;
//끝 노드
private Node tail;
//List 크기
private int size = 0;
public void addFirst(Object input) {
//파라미터로 값을 받았고 새로운 노드를 생성
Node newNode = new Node(input);
//필드의 head 값은 이전 노드를 가리키고 있음으로
//새로운 노드의 next 가 head가 된다는 것은
//새로운 노드가 첫번째로 지정되고 head가 그 다음으로 지정되는 것이다.
newNode.next = head;
//새로운 node가 head가 되었다.
head = newNode;
//노드가 추가 되었음으로 사이즈가 1증가한다.
size++;
//다음 노드가 없다면 그 노드는 tail이 된다.
if (head.next == null){
tail = newNode;
}
}
//끝 부분에 데이터를 추가하는 메서드
public void addLast(Object input) {
//새로운 노드생성
Node newNode = new Node(input);
//만약 저장된 node가없다면 addFirst를 하든 addLast하든 상관이 없다
if(size == 0){
addFirst(input);
}else{
//현재 tail의 다음을 새로운 노드로 지정해주고
tail.next = newNode;
//새로운 노드는 tail이 된다.
tail = newNode;
//사이즈를 1증가 시킨다
size++;
}
}
//내부적 사용으로는 private 가 좋지만 테스트용으로 public사용
Node node(int index){
//첫번째 노드를 가져와 x에 놨다
Node x = head;
//두번째 값을 가져온다.
for (int i = 0 ; i<index; i++){
x = x.next;
}
return x;
}
//노드를 특정 인덱스에 추가시키는 메서드
public void add(int k ,Object input ){
if(k == 0){
addFirst(input);
}else{
Node temp1 = node(k - 1);
Node temp2 = temp1.next;
Node newNode = new Node(input);
temp1.next = newNode;
newNode.next = temp2;
size++;
if(newNode.next == null){
tail = newNode;
}
}
}
//데이터 값 출력을 위한 toString 구현
public String toString(){
//헤드가 없다면 저장된 노드가 없는 것이다
if(head == null){
//빈 괄호를 리턴한다
return "[]";
}
//헤드가 있다면 헤드를 가져와서
Node temp = head;
//괄호를 열고
String str = "[";
while (temp.next != null){
//헤드서부터 끝까지의 node를 더해준다.
str += temp.data + ",";
//temp가 다음 node가 됨으로써 하나씩 다음으로 넘어간다
temp = temp.next;
}
//마지막 노드는 위의 반복문 조건에 해당하지 않기떄문에
//수동으로 마지막 노드를 추가해 준다.
str += temp.data;
return str+"]";
}
//첫번째 것을 지우고 그 값을 리턴한다.
public Object removeFirst() {
//탐색을 위해 첫번째 노드를 찾는다.
Node temp = head;
//첫번째 노드를 지워야하기떄문에 head를 다음으로 변경했다.
head = head.next;
Object returnData = temp.data;
temp = null;
size--;
return returnData;
}
public Object remove(int i) {
if(i == 0){
removeFirst();
return removeFirst();
}else {
Node temp = node(i-1);
Node todoDeleted = temp.next;
temp.next = temp.next.next;
Object returnData = todoDeleted.data;
if(todoDeleted == tail){
tail = temp;
}
todoDeleted = null;
size--;
return returnData;
}
}
public Object removeLast() {
return remove(size-1);
}
public Object get(int i) {
return node(i).data;
}
public int getSize(){
return size;
}
//객체와 객체를 연결하여 만든다 (노드 , 엘리먼트라고도한다)
//inner class로 만들었다
//노드는 데이터와 , 다음 노드에 대한 정보를 포함한다
private class Node{
private Object data;
private Node next;
public Node(Object input) {
this.data = input;
this.next = null;
}
//데이터 값 출력을 위한 toString 구현
public String toString(){
return String.valueOf(this.data);
}
}
}
2.Stack 이란?
과제 3. Stack을 구현하세요.
- int 배열을 사용해서 정수를 저장하는 Stack을 구현하세요.
- void push(int data)를 구현하세요.
- int pop()을 구현하세요.
과제 4. 앞서 만든 ListNode를 사용해서 Stack을 구현하세요.
- ListNode head를 가지고 있는 ListNodeStack 클래스를 구현하세요.
- void push(int data)를 구현하세요.
- int pop()을 구현하세요.
과제 5. Queue를 구현하세요.
- 배열을 사용해서 한번
- ListNode를 사용해서 한번.
스택은 제한적으로 접근할 수 있는 나열된 구조이다. 후입선출(LIFO Last IN First Out)의 자료구조이며 , 접근이 목록의 끝(Top또는 Top Pointer)에서만 일어나기 떄문에 Pushdown List라고도 한다. 스택에서 입력은 push , 출력은 pop ,Top의 위치 데이터 확인은 peek을 사용한다.
스택은 추상자료형(Abstact Data Type)으로 수학적 모델을 가졌으며 구현 방법을 따로 명시하고 있지 않다는 점에서 자료구조와 차이를 보인다. 이러한 특징은 다양한 방법으로 구현될 수 있음을 의미한다
Stack의 사용
운영체제(OS)
-프로그램에서 사용되는 함수들을 스택 자료형에 저장하여 사용한다.
컴파일러
-수학 기호들을 기계어로 변환시 사용한다 (괄호 등을 매칭하는 경우).
가상머신(JVM)
-JVM 내에서 메서드가 실행 , 종료될 때 스택 프레임을 이용하여 관리한다.
Stack 의 구현 (배열로 구현)
Stack은 두가지 (Array와 LinkedList)로 구현할 것이기 떄문에 interface로 만들어 각각 구현하도록 하였다.
public interface Stack {
boolean isEmpty();
boolean isFull();
void push(int item);
int pop();
int peek();
String toString();
}
public class ArrayStack implements Stack{
private int top;
private int stackSize;
private int itemArray[];
public ArrayStack(int stackSize){
//top은 제일 위의 위치한 요소를 가리킨다 . pointer개념
//인덱스에서는 0번이 첫번째이기 떄문에 객체가 생성된 시점에서 요소가 존재하지 않기떄문에
//top은 -1 이다.
top = -1;
//현재 stack의 크기는 배열의 크기와 같다.
this.stackSize = stackSize;
//배열을 생성하고 변수에 넣어준다.
itemArray = new int[this.stackSize];
}
@Override
//스텍이 비었는지 확인하는 메서드
public boolean isEmpty() {
//top이 -1이면 배열에 요소가 없는 상태이다.
return (top == -1);
}
@Override
public boolean isFull() {
//만약 top이 stackSize-1 즉 마지막 인덱스라면 스텍이 꽉찬상태이다.
return (top == this.stackSize-1);
}
@Override
public void push(int item) {
//꽉찬 상태인지 확인한다
if(isFull()){
System.out.println("StackOverflow Error!");
}else{
//top을 1 증가시키고 top에 해당하는 별의 인덱스에 item을 넣어준다.
this.itemArray[++top] = item;
//추가된 item을 출력한다.
System.out.println("inserted Item :" + item);
}
}
//스텍에서 맨위에 요소를 제거하는 메서드
@Override
public int pop() {
//스텍이 비어있다면 pop할 수 없다.
if(isEmpty()){
System.out.println("StackUnderflow Error!");
return 0;
}else {
//스택사이즈를 1줄인다.
stackSize--;
//새로운 배열을 만들고
int [] newItemArray = new int[stackSize];
//이전의 배열의 요소를 하나씩 새로운 배열에 넣어준다.
for (int i =0; i<newItemArray.length; i++) {
newItemArray[i] = itemArray[i];
}
//새로운 배열을 itmeArray 변수에 담아주고
itemArray = newItemArray;
//top을 1감소 시켜준 후 해당값을 리턴한다.
return itemArray[--top];
}
}
//제일 위에 위치한 것을 리턴함
@Override
public int peek() {
//스택이 비어 있다면 peek을 찾을 수 없다
if(isEmpty()){
System.out.println("StackUnderflow Error! -can not found peek");
return 0;
}
//현재 top의 요소를 리턴한다.
return itemArray[top];
}
//stack을 문자열로 리턴하는 메서드
public String toString() {
//만약 스택이 비어있다면 빈괄호를 리턴한다.
if (stackSize == 0) {
//빈 괄호를 리턴한다
return "[]";
}
//괄호를 열어 주고 변수에 담는다.
String array = "[";
//열린괄호안에 itemArray의 요소를 하나씩 콤마와함께 넣어준다.
for (int i =0; i<itemArray.length-1; i++) {
if (!(i == itemArray.length-1)) {
array += itemArray[i] + ",";
}
}
//만약 마지막 요소라면 여기서 콤마없이 추가된다
array += itemArray[itemArray.length - 1];
//괄호를 닫고
array = array + "]";
//리턴한다.
return array;
}
}
'JAVA' 카테고리의 다른 글
| JAVA 스터디 9 - 추상 클래스와 추상메서드 (0) | 2021.03.18 |
|---|---|
| JAVA 스터디 8 - 상속 (0) | 2021.03.18 |
| JAVA 스터디 6 - JUNIT5 (0) | 2021.02.08 |
| JAVA 스터디 5 - switch expression (자바 12부터 추가됨) (0) | 2021.02.05 |
| JAVA 스터디 4- 제어문,반복문 (0) | 2021.02.03 |
