WonYong-Jang commented 6 years ago

링크드 리스트

자바는 객체지향 언어이기 때문에 노드는 객체로 만들기 좋은 대상
노드 객체는 리스트의 내부 부품이기 때문에 외부에는 노출되지 않는 것이 좋다. ==> private
사용자는 이 객체에 대해서 알 필요가 없습니다. 단지 값을 넣고 빼는 것으로 충분
head : 처음 노드 위치 기억
tail : 노드의 끝 위치 ( 링크드 리스트는 tail 없이도 구현 가능 , 하지만 리스트 끝 데이터 수정하는 작업을 할때 효율적으로 하기 위해서 사용)

package com.company.etc;

class NodeList {
    private Node head; // 맨 처음 
    private Node tail; // 맨 끝 
    private int size; // 노드 갯수 

    private class Node{
        int data;
        Node next; // 노드의 다음 노드를 가르킴 

        public Node(int data)
        {
            this.data = data;
        }
    }

    public void addFirst(int data) // 맨 앞 노드 추가 
    {
        Node newNode = new Node(data); // 노드 생성 

        newNode.next = head; // 새로 만든 노드를 이전에 헤드 였던에랑 연결!!!

        head = newNode; // haed가 새로 만들어진 노드를 가르키도록 ! 

        if(head.next == null)
        {
            tail = head; // 현재 노드가 하나밖에 없어서 head 의 다음이 없다면 그곳이 tail 자리도 되니까 
        }

        size++;
    }
    public void addLast(int data)
    {
        Node newNode = new Node(data);

        if(size == 0) {
            addFirst(data);
        }

        tail.next = newNode; // 이전 tail 의 노드 값과 새로운 노드 연결 
        tail = newNode; // tail 을 새로운 노드로 갱신 
        size++;
    }
    public Node node(int index) // 특정 인덱스 노드 찾아가기 
    {
        Node target = head;
        for(int i=0; i< index; i++)
        {
            target = target.next;
        }
        return target;
    }
    public void add(int index, int data) // 특정 인덱스 노드에 삽입 
    {
        if(size ==0) {
            addFirst(data);
        }
        else 
        {
            Node preNode = node(index-1); // 그전 노드 가져오기 
            Node nextNode = preNode.next; // 그 다음 노드 가져오기 

            Node newNode = new Node(data); // 중간에 삽입할 노드 
            preNode.next = newNode; // 이전 노드랑 연결 
            newNode.next = nextNode; // 새로만든 노드를 다음 노드와 연결 
            size++;

            if(newNode.next == null ) // 다음 노드가 없다는건 해당 노드가 끝 이니까 tail 로 갱신 
            {
                tail = newNode;
            }
        }
    }
    public int removeFirst() { // 가지고 있던 데이터 리턴이 원칙 

        Node temp = head; // 헤드가 가르키고 있는 첫번째 값을 임시로 저장 (삭제전)

        head = temp.next; // 헤드를 다음 노드를 가르키게 

        int deleteDate = temp.data; // 삭제 시킬 데이터 
        temp = null; // 삭제 

        size--;

        return deleteDate;
    }
    public int remove(int k) {

        if(k ==0) {
            return removeFirst();
        }
        Node temp = node(k-1); // 삭제시킬 바로 이전 노드 가져오기 

        Node todoDelete = temp.next; // 삭제할 노드 

        temp.next = temp.next.next; // 삭제 할 노드 다음 노드 

        int returnData = todoDelete.data;

        if(todoDelete == tail)
        {
            tail = temp; // 이전 노드로 갱신 
        }

        size--;
        todoDelete = null;
        return returnData;
    }
    public int removeLast()
    {
        return remove(size-1);
    }
    public String toString() {

        if(head == null) {
            return "[ ]";
        }

        Node temp = head;

        String str ="[";

        while(temp.next != null)
        {
            str += temp.data + ",";
            temp = temp.next;
        }
        str += temp.data;
        return str+"]";
    }
}

public class LinkedList {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        NodeList list = new NodeList();
        list.addFirst(10);
        list.addFirst(20);
        list.addLast(30);
        System.out.println(list.removeFirst());
        System.out.println(list);
    }

}

1406 번 직접 구현 해보기 ! 1158

WonYong-Jang commented 5 years ago

스택

Last In First Out 가장 최근에 입력된 데이터를 top 이라고 하며 스택은 top 에서만 삽입, 삭제, 읽기 동작이 발생 가능
push, pop, peek
배열로 구현
배열에 실제 데이터를 저장하기 때문에 배열의 크기를 미리 정해 주어야 하기 때문에 배열이 꽉 차있는지 확인 하는 작업이 필요

public class ArrayStack {

    private int top;
    private int maxSize;
    private Object[] stackArray;

    // 배열 스택 생성,  스택의 최대 크기로 생성
    public ArrayStack(int maxSize){

        this.maxSize = maxSize;
        this.stackArray = new Object[maxSize];
        this.top = -1;
    }

    // 스택이 비어있는지 체크
    public boolean empty(){
        return (top == -1);
    }

    // 스택이 꽉찼는지 체크
    public boolean full(){
        return (top == maxSize-1);
    }

    // 스택에 item 입력
    public void push(Object item){

        if(full()) throw new ArrayIndexOutOfBoundsException((top+1)+">=" + maxSize);

        stackArray[++top] = item;
    }

    // 스택의 가장 위의 데이터 반환
    public Object peek(){

        if(empty()) throw new ArrayIndexOutOfBoundsException(top);

        return stackArray[top];
    }

    // 스택의 가장 위의 데이터 제거
    public Object pop(){

        Object item = peek();

        top--;

        return item;
    }

}

링크드 리스트를 이용하여 구현

배열을 이용한 스택의 구현의 가장 큰 단점은 처음 생성한 크기를 바꿀 수 없다는 것
이를 해결하기 위해 링크드 리스트로 스택 구현 ( 스택이 다 찼는지 여부 체크할 필요 없음)

class ListStack {

    private Node top;

    // 노드 class 단순연결리스트와 같다.
    private class Node{

        private Object data;
        private Node nextNode;

        Node(Object data){
            this.data = data;
            this.nextNode = null;
        }
    }

    // 생성자, stack이 비어있으므로 top은 null이다.
    public ListStack(){
        this.top = null;
    }

    // 스택이 비어있는지 확인
    public boolean empty(){
        return (top == null);
    }

    // item 을 스택의 top에 넣는다.
    public void push(Object item){

        Node newNode = new Node(item);
        newNode.nextNode = top;
        top = newNode;

    }

    // top 노드의 데이터를 반환한다.
    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        return top.data;
    }

    // top 노드를 스택에서 제거한다.
    public Object pop(){

        Object item = peek();
        top = top.nextNode;
        return item;
    }
}

WonYong-Jang commented 5 years ago

스택 계산기 (전위/ 중위/ 후위) http://yahma.tistory.com/5

http://yahma.tistory.com/7?category=640326

WonYong-Jang commented 4 years ago

링크드 리스트 사이클 판별 알고리즘

토끼와 거북이 알고리즘

두개의 포인터를 사용하는데 한개의 포인터는 한칸씩 이동(거북이) / 다른 한개의 포인터는 두칸씩 이동(토끼) 해서 진행하면 사이클이 존재한다면 토끼가 반드시 거북이를 잡는다는 알고리즘
문제 leetcode 141


public class Solution {

    public boolean hasCycle(ListNode head) {

        if(head == null) return false;

        boolean result = false;

        ListNode hare = head; // 토끼 
        ListNode tortoise = head; // 거북이

        while(true)
        {
            if(hare == null || hare.next == null) break; // 사이클이 없다면 토끼먼저 도착하므로 토끼만 확인 

            tortoise = tortoise.next;
            hare = hare.next.next;

            if(hare == tortoise) {
                result = true;
                break;
            }

        }

        return result;
    }

}

두 링크드 리스트 만나는 지점 찾기

leetcode 160 Intersection of Two Linked Lists
두 링크드 리스트를 한칸씩 전진시키고 길이가 동일하고 둘다 널값으로 끝나면 만나는 지점 없는 것!!
짧은 길이의 링크드 리스트가 먼저 널값으로 도착하면 다른 링크드 리스트 시작점으로 잡고 다시 출발
이렇게 했을때 만나면 교차점! 이렇게 출발점을 변경하면서 이동했는데도 둘다 널값으로 끝나면 교차점 없음!!

WonYong-Jang commented 4 years ago

더블 링크드 리스트 reverse

해커랭크 Reverse a doubly linked list

WonYong-Jang / algorithm

링크드 리스트 ( LinkedList ), 사이클 / 이중 연결리스트 || 스택 #10