LinkedList,Stack,Queue 구현 및 테스트 - 백기선 자바라이브스터디

LinkedList란

---

링크드리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있습니다 

위의 그림에서 알 수 있듯이 링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있습니다 

class Node
{
   Node next; // 다음 요소의 주소를 저장
   Object obj; // 데이터를 저장 
 }

---

삭제

링크드 리스트의 삭제는 배열보다 간단합니다. 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 됩니다. 단지 하나의 참조만 변경하면 삭제가 이루어지는 것입니다.

 

배열은 삭제를 하면 다른 요소들이 앞으로 땡겨져야 하기 때문에 복사가 일어나지만 : O(n)

링크드리스트는 그런 과정이 필요가 없습니다 : O(1)

 

---

추가

새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 빠릅니다

: O(1)

 

---

배열과 링크트리스트  비교

컬렉션	읽기(접근시간)	추가 / 삭제	비고
ArrayList	빠르다(O(1))	느리다(O(n))	순차적인 추가삭제(앞,뒤)는 더 빠름. 하지만 메모리 복사를 하는 등 비효율적인 메모리 사용
LinedList	느리다 (O(n))	빠르다(O(1))	데이터가 많을 수록 접근하는데 O(n)이기에 비효율적

---

LinkedList를 구현 

---

ListNode.java 

public class ListNode<T>{
    private T data; // int를 저장하는 데이터
    private ListNode next;


    public ListNode(T data, ListNode next) {
        this.data = data;
        this.next = next;
    }

    public ListNode add(ListNode newElement){
        if (this.next == null){
            this.next = newElement;
            return this;
        }

        ListNode nextNode = this.next;
        while (nextNode.next != null){
            nextNode = nextNode.next;
        }

        nextNode.next = newElement;

        return this;
    }



    public ListNode<T> add(ListNode<T> head, ListNode<T> nodeToAdd, int position){
        if(position==0){
            nodeToAdd.next = head.next;
            head.next = nodeToAdd;

        }else{
            ListNode<T> pointer = head;
            for (int i = 0; i < position; i++) {
                pointer = pointer.getNext();
            }
            nodeToAdd.next = pointer.next;
            pointer.next = nodeToAdd;
        }
        return head;
    }

    public ListNode<T> remove(ListNode<T> head, int positionToRemove){
        ListNode<T> deleteNode;
        if(positionToRemove==0){
            deleteNode = head.next;
            head.next = deleteNode.next;
        }else{
            ListNode<T> pointer = head.next;
            for(int i =1; i< positionToRemove-1; i++){
                pointer = pointer.getNext();
            }
            deleteNode = pointer.getNext();
            pointer.next = deleteNode.getNext();
            deleteNode.next = null;

        }
        return deleteNode;
    }

    public boolean contains(ListNode head, ListNode nodeToCheck){
        ListNode<T> pointer = head.next;
        while(pointer!=null){
            if(pointer.data==nodeToCheck.getData()){
                return true;
            }
            pointer = pointer.next;
        }
        return false;
    }


    public T getData() {
        return data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

    public void printForEach(){
        ListNode nextNode = this;

        while (nextNode != null){
            System.out.println(nextNode);
            nextNode = nextNode.next;
        }
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "data=" + data +
                '}';
    }
}

---

ListNodeTest.java

class ListNodeTest {

    private ListNode<Integer> listNode;
    private static final int[] data = {10,20,30,40,50};
    private static LinkedList<Integer> expList;

    @BeforeEach
    void eachSetting(){
        expList = new LinkedList<>();

        ListNode headNode = new ListNode(null,null);
        ListNode firstNode = new ListNode(10,null);
        ListNode secondNode = new ListNode(20,null);
        ListNode thirdNode = new ListNode(30,null);
        ListNode fourthNode = new ListNode(40,null);
        ListNode fifthNode = new ListNode(50,null);

        this.listNode = headNode;
        headNode.setNext(firstNode);
        firstNode.setNext(secondNode);
        secondNode.setNext(thirdNode);
        thirdNode.setNext(fourthNode);
        fourthNode.setNext(fifthNode);
    }

    @Test
    @DisplayName("add 메서드 테스트")
    void add(){
        listNode = listNode.add(listNode,new ListNode<>(11,null),1);
        listNode.printForEach();
        for (int i : data) {
            expList.add(i);
        }
        expList.add(1,11);

        listNode = listNode.getNext();
        for(int i=0; i<expList.size(); i++){
            Assertions.assertEquals(expList.get(i),listNode.getData(),()->"add한 결과가 expList와 일치하지 않습니다.");
            listNode = listNode.getNext();
        }
    }

    @Test
    @DisplayName("delete 메서드 테스트")
    void remove(){

        Assertions.assertEquals(10,listNode.remove(listNode,0).getData());
        listNode.printForEach();
        Assertions.assertEquals(30,listNode.remove(listNode,1).getData());
    }


    @Test
    @DisplayName("노드가 리스트에 포함되있는지 테스트")
    void contain(){
        assertTrue(listNode.contains(listNode,new ListNode<>(30,null)),"30이 존재해야만 한다");
    }
}

---

실행결과

---

Stack 구현 

---

StackImpl.java

public class StackImpl {
    private int size;
    private int point;
    private Integer[] elementData;

    public StackImpl(int size) {
        this.size = size;
        this.point = 0;
        this.elementData = new Integer[size];
    }

    public void push(int data){
        if(size==point)throw new IndexOutOfBoundsException("더이상 스택에 data를 추가할 수 없습니다");

        elementData[point++] = data;
    }

    public int pop(){
        return elementData[--point];
    }


}

---

StackImplTest.java

class StackImplTest {



    @Test
    @DisplayName("push 테스트")
    void push(){
        StackImpl stack = new StackImpl(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        IndexOutOfBoundsException exception = assertThrows(IndexOutOfBoundsException.class, () -> stack.push(60));
        assertEquals("더이상 스택에 data를 추가할 수 없습니다",exception.getMessage());
    }

    @Test
    @DisplayName("pop 테스트")
    void pop(){
        StackImpl stack = new StackImpl(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);
        assertEquals(50,stack.pop());
        assertEquals(40,stack.pop());
    }

}

---

실행결과

---

앞서 만든 ListNode를 사용해서 Stack을 구현 

---

ListNodeStack.java

public class ListNodeStack {
    private ListNode<Integer> head;
    private int size;

    public ListNodeStack(){
        head = new ListNode<>(null,null);
        size = 0;
    }

    public void push(int data){
        head.add(head,new ListNode<>(data,null),size);
        size++;
    }

    public int pop(){
        return head.remove(head,size--).getData();
    }
}

---

ListNodeStackTest.java

class ListNodeStackTest {

    @Test
    @DisplayName("push 테스트")
    void stackTest(){
        ListNodeStack stack = new ListNodeStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);

        stack.pop();

        assertEquals(30,stack.pop());
    }
}

---

실행결과

---

Queue 구현

---

QueueImpl.java

public class QueueImpl {
    private Integer[] elementData;
    private int offerPoint;
    private int pollPoint;
    private int size;

    public QueueImpl(int size){
        this.size = size;
        this.elementData = new Integer[size];
        this.offerPoint = 0;
        this.pollPoint = 0;
    }

    public void offer(int data){
        elementData[offerPoint++] = data;
        offerPoint %= size;
    }

    public int poll(){
        int deleteData = elementData[pollPoint++];
        pollPoint %= size;
        return deleteData;
    }
}

---

QueueImplTest.java

class QueueImplTest {

    @Test
    @DisplayName("offer, poll 큐 테스트")
    void allTest(){
        QueueImpl queue = new QueueImpl(5);
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        queue.offer(40);
        queue.offer(50);

        queue.poll();
        queue.offer(60);

        queue.poll();
        queue.poll();
        queue.poll();
        queue.poll();

        assertEquals(60,queue.poll());

    }
}

---

실행결과

---

ListNode를 사용한 큐 구현

---

ListNodeQueue.java

public class ListNodeQueue {
    private ListNode<Integer> head;
    private int size;

    public ListNodeQueue(){
        head = new ListNode<>(null,null);
        size = 0;
    }

    public void offer(int data){
        head.add(head,new ListNode<>(data,null),size);
        size++;
    }

    public int poll(){
        size--;
        return head.remove(head,0).getData();
    }


}

---

ListNodeQueueTest.java

class ListNodeQueueTest {

    @Test
    @DisplayName("offer poll 전체테스트")
    void queueTest(){
        ListNodeQueue queue = new ListNodeQueue();
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        queue.poll();

        assertEquals(20,queue.poll());
    }
}

---

실행결과