패스트캠퍼스 챌린지 3일차

스택 (Stack)

 • 데이터를 제한적으로 접근할 수 있는 구조

  - 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

  - 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

  - LIFO(Last-In, First-Out) 정책, 큐와 반대

 

• 주요기능

 - push() : 데이터를 스택에 넣기

 - pop() : 데이터를 스택에서 꺼내기

 

• 사용법

Stack<자료형> stack = new Stack<>();

stack.push(값)

stack.pop(값)

 

링크드 리스트(Linked List, 연결 리스트)

 - 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

 - 데이터와 다음데이터의 주소를 저장하는 공간을 같이 저장

 - 중간에 있는 데이터를 삭제해도 포인터 (데이터주소)를 이용하여 찾아갈 수 있다.

 

기본 구조와 용어

 - 노드(Node) : 데이터 저장 단위 (데이터값, 포인터) 로 구성 

 - 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

 

public class Node<T> {
	T data;
    Node<T> next = null;
    
    public Node(T data){
    	this.data = data;
    }
    
}

// 노드와 노드 연결 : 노드 인스턴스간 연결
Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node2 = new Node<Integer>(2);

// 링크드 리스트에 데이터 추가
node1.next = node2;
Node head = node1;

public class SingleLinkedList<T>{
	public Node<T> head = null;
    
    public class Node<T>{
    T data;
    Node<T> next = null;
    
    public Node(T data){
    	this.data = data;
    }
    
    public void addNode(T data){
    	if(head == null){
        	head = new Node<T>(data);
    	}else{
        	Node<T> node = this.head;
            while(node.next != null){
            	node = node.next;
            }
            node.next = new Node<T>(data)
        }
    }
    
    public void printAll(){
    	if(head != null){
        	Node<T> node = this.head;
            System.out.println(node.data);
            while(node.next != null){
            	node = node.next;
                System.out.println(node.data);
            }
        }
    }
}

SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<Integer>();
MyLinkedList.addNode(1);
MyLinkedList.head.data // 2
MyLinkedList.addNode(2);
MyLinkedList.addNode(3);
MyLinkedList.printAll() // 1,2,3

• 장단점

 - 장점 : 데이터 공간을 미리 할당하지 않아도 됨 (배열은 미리 데이터 공간 할당)

 - 단점 : 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음

         연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림

         중간 데이터 삭제 시, 앞 뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

• 링크드 리스트 데이터 사이에 데이터 추가

public Node<T> search(T data){
	if(this.head == null){
    	return null;
    }else{
    	Node<T> node = this.head;
        while(node != null){
        	if(node.data == data){
            	return node;
            }else{
            	node = node.next
            }
            return null;
        }
    }
}

public void addNodeInsied(T data, T isData){
	Node<T> searchedNode = this.search(isData);
    
    if(searchedNode == null){
    	this.addNode(data);
    }else{
    	Node<T> nextNode = searchedNode.next;
        searchedNode.next = new Node<T>(data);
        searchedNode.next.next = nextNode;
    }
}

// 위에 있는 SingleLinkedList 
SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<Integer>();
MyLinkedList.addNode(1);
MyLinkedList.addNode(2);
MyLinkedList.addNode(3);

MyLikedList.addNodeInsied(6,3);

 

• 데이터의 중간노드 삭제

public boolean delNode(T isData){
	if(this.head == null){
    	return false;
    }else{
    	Node<T> node = this.head;
        // head에 있는 노드가 해당 데이터인지 여부
        if(node.data == isData){
        	this.head = this.head.next;
            return true;
        }else{
        	if(node.next.data == isData){
            	node.next = node.next.next; // node의 포인터값 다다음으로 바꾸기
                return true;
            }else{
            	node = node.next
            }
        }
        return false;
    }
}

MyLinkedList.delNode(3) // 3이 제거되며 뒤에꺼로 포인터가 계속 연결된다.

 

 

 

3일차 인증

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC