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

[WonYong-Jang]

링크드 리스트

• 자바는 객체지향 언어이기 때문에 노드는 객체로 만들기 좋은 대상
• 노드 객체는 리스트의 내부 부품이기 때문에 외부에는 노출되지 않는 것이 좋다. ==> 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]

스택

• 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]

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

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

[WonYong-Jang]

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

토끼와 거북이 알고리즘

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

• 문제 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]

더블 링크드 리스트 reverse

해커랭크 Reverse a doubly linked list