코딩쿠의 코드 연대기

Java 자료구조) ArrayList, LinkedList (Stack, Queue) 본문

코딩스터디/JAVA스터디

Java 자료구조) ArrayList, LinkedList (Stack, Queue)

코딩쿠 2024. 11. 9. 23:51

학습목표

  • LinkedList를 구현
  • Stack을 구현
    • int 배열을 사용해서 정수 저장하는 Stack (push, pop 구현)
    • ListNode head를 가지고 있는 ListNodeStack 클래스 구현 (push, pop 구현)
  • Queue을 구현
    • int 배열을 사용해서 정수 저장하는 Queue(push, pop 구현)
    • ListNode head를 가지고 있는 ListNodeQueue 클래스 구현 (push, pop 구현)

LinkedList

Java에서 LinkedList는 List 인터페이스를 구현하는 자료 구조입니다. ArrayList와 같이 데이터를 순차적으로 저장하지만, 내부적으로는 노드를 사용하여 데이터를 연결 리스트 형태로 저장한다는 점이 다릅니다.

 

LinkedList의 특징

  • 연결 리스트 구조: 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있습니다. 이러한 구조 덕분에 데이터 삽입, 삭제가 빠릅니다.
  • 순차 접근: 인덱스를 사용하여 특정 위치의 데이터에 접근할 수 있지만, ArrayList보다 느립니다.
  • 동적 크기: 필요에 따라 크기가 동적으로 조절됩니다.

LinkedList의 장점

  • 삽입, 삭제 효율성: 연결 리스트 구조 덕분에 중간에 데이터를 삽입하거나 삭제할 때, ArrayList처럼 데이터를 이동시킬 필요가 없어 효율적입니다.
  • 유연한 크기: 배열처럼 미리 크기를 지정할 필요 없이, 데이터 추가에 따라 크기가 동적으로 증가합니다.

LinkedList의 단점

  • 느린 검색: 특정 위치의 데이터를 검색하려면 처음부터 순차적으로 노드를 따라가야 하므로 ArrayList보다 검색 속도가 느립니다.

LinkedList의 주요 메서드

  • add(E e): 리스트의 끝에 요소를 추가합니다.
  • add(int index, E element): 지정된 위치에 요소를 추가합니다.
  • get(int index): 지정된 위치의 요소를 반환합니다.
  • remove(int index): 지정된 위치의 요소를 제거합니다.
  • size(): 리스트의 크기를 반환합니다.

LinkedList 사용 예시

Java

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // 요소 추가
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 요소 출력
        System.out.println(list); // [Apple, Banana, Cherry]

        // 특정 위치에 요소 추가
        list.add(1, "Grape");
        System.out.println(list); // [Apple, Grape, Banana, Cherry]

        // 특정 위치의 요소 제거
        list.remove(2);
        System.out.println(list); // [Apple, Grape, Cherry]

        // 특정 위치의 요소 가져오기
        System.out.println(list.get(1)); // Grape
    }
}

LinkedList는 언제 사용하는 것이 좋을까요?

  • 데이터 삽입, 삭제가 빈번하게 발생하는 경우
  • 데이터의 순서가 중요하고, 검색은 자주 하지 않는 경우

참고 자료

구현

package linkedList;

public class LinkedList {
    /*
     * ToDo
     * 1. Node 클래스 정의
     * 2. LinkedList 클래스 구현
     * 3. 메서드 구현 (add, remove, contains, display)
     */
    
    private Node head; // 리스트의 첫 번째 노드를 가리키는 포인터
    
    public LinkedList() {
        this.head = null; // 생성자: 리스트의 초기 상태는 비어있음
    }
    
    // 리스트 끝에 새로운 노드를 추가하는 메서드
    public void add(int data) {
        Node newNode = new Node(data); // 추가할 새 노드 생성
        if(head == null) { // 리스트가 비어있는 경우
            head = newNode; // 새 노드를 첫 노드로 설정
        } else {
            Node current = head; // 리스트의 첫 노드부터 시작
            while (current.next != null) { // 마지막 노드까지 이동
                current = current.next;
            }
            current.next = newNode; // 마지막 노드의 다음으로 새 노드를 연결
        }
    }
    
    // 리스트에서 특정 데이터를 가진 노드를 제거하는 메서드
    public void remove(int data) {
        if (head == null) return; // 리스트가 비어있으면 종료
        if (head.data == data) { // 첫 번째 노드가 삭제 대상인 경우
            head = head.next; // 첫 번째 노드를 제거하고 다음 노드를 첫 노드로 설정
            return;
        }
        Node current = head; // 리스트의 첫 노드부터 시작
        while (current.next != null) { // 리스트의 끝까지 탐색
            if(current.next.data == data) { // 삭제할 데이터를 가진 노드 발견
                current.next = current.next.next; // 해당 노드를 리스트에서 제거
                return;
            }
            current = current.next; // 다음 노드로 이동
        }
    }
    
    // 리스트의 모든 노드를 출력하는 메서드
    public void display() {
        Node current = head; // 첫 노드부터 시작
        while (current != null) { // 리스트의 모든 노드를 탐색
            System.out.print(current.data + " -> "); // 각 노드의 데이터를 출력
            current = current.next; // 다음 노드로 이동
        }
        System.out.println("null"); // 리스트의 끝을 표시
    }
    
    // 리스트에 특정 데이터가 포함되어 있는지 확인하는 메서드
    public boolean contains(int data) {
        Node current = head; // 첫 노드부터 시작
        while (current != null) { // 리스트의 모든 노드를 탐색
            if (current.data == data) { // 데이터가 일치하는 경우
                return true; // 데이터가 존재함
            }
            current = current.next; // 다음 노드로 이동
        }
        return false; // 데이터가 존재하지 않음
    }
    
    // 노드 클래스 정의: 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가짐
    public class Node {
        int data; // 노드가 저장하는 데이터
        Node next; // 다음 노드를 가리키는 포인터
        
        public Node(int data){
            this.data = data; // 데이터 초기화
            this.next = null; // 다음 노드의 초기값은 null
        }
    }
}

 위 코드에서 추가할 내용이 있다면 지금은 add 메서드가 List의 끝에만 추가할 수 있는데, 특정 위치에 추가할 수 있도록 코드를 확장할 필요가 있어보인다. 

Stack, Queue 배열로 구현

Stack은 후입선출(LIFO, Last In First Out) 구조의 자료구조로, 마지막에 추가된 요소가 가장 먼저 제거됩니다. Stack은 일반적으로 배열이나 연결 리스트로 구현할 수 있으며, 주요 기능으로 `push`와 `pop` 메서드를 갖추고 있습니다. 

구현

package linkedList;


public class Stack {
	/*
	 * ToDo
	 * 1. int 배열을 사용해서 정수를 저장하는 Stack을 구현하세요.
	 * 2. void push(int data)를 구현하세요.
	 * 3. int pop()을 구현하세요.
	 * */
	
	private int[] stackArray;
	private int top = -1;
	private int size;
	
	
	// 생성자: Stack의 크기를 초기화
	public Stack(int size) {
		this.size = size;
		stackArray = new int[this.size];
	}
	// 데이터를 Stack에 추가하는 메서드
	public void push(int data) {
		//stack이 가득차 있는가??
		if(size - 1 == top) {
			System.out.println("Stack이 가득차 있습니다.");
		} else {
			top++;
			stackArray[top] = data;
			System.out.println("Stack에 " + data + "추가완료");
		}
	}
	// 데이터를 Stack에서 꺼내는 메서드
	public int pop() {
		//top이 -1인가?
		if(top == -1) {
			System.out.println("Stack안에 내용이 없습니다.");
			return -1;
		}else {			
			int popInt = stackArray[this.top--];
			System.out.println("꺼낸 값 : " + popInt);
			return popInt;
		}		
	}
	
	// Stack이 비어있는지 확인하는 메서드
    public boolean isEmpty() {
        return top == -1;
    }
    
    // Stack이 가득 찼는지 확인하는 메서드
    public boolean isFull() {
        return top == size - 1;
    }
}

 

Queue는 선입선출(FIFO, First In First Out) 구조의 자료구조로, 먼저 추가된 요소가 가장 먼저 제거됩니다. Queue는 배열 또는 연결 리스트로 구현할 수 있으며, 기본적으로 enqueue(추가)와 dequeue(제거) 메서드를 갖추고 있습니다.

구현

package linkedList;

public class Queue {
	private int[] queueArray;
	private int top = -1;
	private int size;
	
	//생성자: Queue의 크기를 초기화
	public Queue(int size) {
		this.size = size;
		queueArray = new int[this.size];
	}
	// 데이터를 Queue에 추가하는 메서드
	public void push(int data) {
		//배열이 차 있는가?
		if(size - 1 == top) {
			System.out.println("Queue이 가득차 있습니다.");
		}else {
			top++;
			queueArray[top] = data;
			System.out.println("Queue에 " + data + "추가완료");
		}
	}
	// 테이터를 Queue에 꺼내는 메서드
	public int pop() {
		//top이 -1인가?
		if(top == -1) {
			System.out.println("queue안에 내용이 없습니다.");
			return -1;
		}else {
			int popInt = queueArray[0];
			System.out.println("꺼낸 값 : " + popInt);
			for(int i = 0; i <this.top; i++ ) {
				queueArray[i] = queueArray[i+1];
			}
			top--;
			return popInt;
		}		
	}
	// Queue이 비어있는지 확인하는 메서드
    public boolean isEmpty() {
        return top == -1;
    }
    
    // Queue이 가득 찼는지 확인하는 메서드
    public boolean isFull() {
        return top == size - 1;
    }
}

Stack, Queue ListNode로 구현

위에서 구현한 LinkedList를 활용하여 'ListNode'를 이용한 Stack과 Queue를 구현해봤다.

package linkedList;


public class LinkedListStackQueue {
	/*
	 * ListNode head를 가지고 있는 ListNodeStack 클래스 구현
	 * ListNode head를 가지고 있는 ListNodeQueue 클래스 구현
	 * */
	private Node head;
	
	public LinkedListStackQueue() {
		this.head = null;
	}
	
	public void push(int data) {
		Node newNode = new Node(data);
		if(head == null) {
			head = newNode;
		}else {
			Node current = head;
			while (current.next != null) {
				current = current.next;
			}
			current.next = newNode;
		}
	}
	public int stackPop() {
	    if (head == null) {
	        System.out.println("pop을 할 값이 없습니다.");
	        return -1;
	    }
	    
	    // 단일 노드만 있을 경우, head를 제거
	    if (head.next == null) {
	        int stackData = head.data;
	        head = null; // 리스트가 비어 있게 설정
	        System.out.println("stack Pop : " + stackData);
	        return stackData;
	    }
	    
	    // 여러 노드가 있을 경우, 마지막 노드까지 이동하여 pop
	    Node current = head;
	    Node previous = null;
	    
	    // 마지막 노드로 이동하며 이전 노드 추적
	    while (current.next != null) {
	        previous = current;
	        current = current.next;
	    }
	    
	    // 마지막 노드를 pop
	    int stackData = current.data;
	    previous.next = null; // 이전 노드의 next를 null로 설정하여 마지막 노드 제거
	    System.out.println("stack Pop : " + stackData);
	    return stackData;
	}

	
	public void display() {
        Node current = head;
        while (current != null) { // 리스트의 모든 노드를 탐색
            System.out.print(current.data + " -> "); // 각 노드의 데이터를 출력
            current = current.next;
        }
        System.out.println("끝"); // 리스트의 끝을 표시
    }
	
	public int queuePop() {
		if(head == null) {
			System.out.println("pop을 할 값이 없습니다.");
			return -1;
		}else {
			int stackData;
			stackData = head.data;
			head = head.next;
			//			current = null;
	        System.out.println("stack Pop : " + stackData);
	        return stackData;
		}		
	}
	
	public class Node {
		int data;
		Node next;
		public Node(int data) {
			this.data = data;
			this.next = null;
		}
	}
	
}

테스트

package linkedList;

public class LinkedListExample {

	public static void main(String[] args) {
		System.out.println("--------- - ---------- - -----------");
		System.out.println("--- linkedlist 활용 stack, Queue ---");
		System.out.println("--------- - ---------- - -----------");
		LinkedListStackQueue myStackList = new LinkedListStackQueue();
		myStackList.push(11);
		myStackList.push(22);
		myStackList.push(33);
		
		myStackList.display();
		myStackList.push(44);
		myStackList.display();
		myStackList.stackPop();
		
		myStackList.display();
		myStackList.stackPop();
		
		myStackList.display();
		myStackList.stackPop();
		myStackList.display();
		LinkedListStackQueue myQueueList = new LinkedListStackQueue();
		myQueueList.push(111);
		myQueueList.push(222);
		myQueueList.push(333);
		
		myQueueList.display();
		
		myQueueList.queuePop();
		myQueueList.push(444);
		myQueueList.display();
		
		myQueueList.queuePop();
		myQueueList.push(555);
		myQueueList.display();
		
		myQueueList.queuePop();
		
		myQueueList.display();
	}

}

결과값

--------- - ---------- - -----------
--- linkedlist 활용 stack, Queue ---
--------- - ---------- - -----------
11 -> 22 -> 33 -> 끝
11 -> 22 -> 33 -> 44 -> 끝
stack Pop : 44
11 -> 22 -> 33 -> 끝
stack Pop : 33
11 -> 22 -> 끝
stack Pop : 22
11 -> 끝
111 -> 222 -> 333 -> 끝
stack Pop : 111
222 -> 333 -> 444 -> 끝
stack Pop : 222
333 -> 444 -> 555 -> 끝
stack Pop : 333
444 -> 555 -> 끝

'코딩스터디 > JAVA스터디' 카테고리의 다른 글

java 자료구조) 이진트리 (BinrayTree)  (0) 2024.11.11
객체지향 프로그래밍 (OOP)  (5) 2024.11.10
Java 클래스  (12) 2024.11.08
Java 조건문, Java 반복문  (6) 2024.11.03
Java 연산자  (2) 2024.10.26
'코딩스터디/JAVA스터디' Related Articles more