List 구현

개요

•  LinkedList원리
  • Node를 통해서 객체들을 연결을 한 상태로 Node 내부에 data와 nextNode 주소, prevNode 주소 등이 들어갈 수 있다.
  • 구현된 LinkedList 이용시 중간에 값 추가, 중간 값 삭제 등 배열보다 높은 성능을 보여준다.

 

• LinkedList 구현의 필요성
  • 회전하는 순서 같이 LinkedList의 원리로 구현할 수 있는 부분들이 LinkedList에 구현이 되어있지 않다.
    
    • ex) 1,2,3 이 저장된 list를 get(int index)을 통해서 뽑아낼때 indexrk list Node 수보다 많으면 예외발생
  • 이 외에도 LinkedList를 직접 구현해야되는 상황이 생길시 구현을 할 줄 알아야한다.
    
    
• 구현 순서
  1. LinkedList : 평소에 사용하는 LinkedList와 동일
  2. CircleLinkedList : 마지막 Node next에 첫 Node의 주소 넣음
  3. DoubleLinkedList : prev Node를 추가하여 이전으로 돌아가는 기능을 수행
  4. CircleDoubleLinkedList 구현 : 첫 Node의 prev에 마지막 Node 주소를 넣고 마지막 Node next에 첫 Node의 주소 넣음
     
     
• 전체 코드
  • https://github.com/taewan625/java/commits/main
  • LinkedListImpl_1step code부터 확인

 

 

1.  LinkedList 구현

• 구현

public class LinkedListImpl {
    public static void main(String[] args) {}
}
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
    @Override
    public String toString() {
        return data + "";
    }
}

class LinkedList {
    Node head;

    public LinkedList() {
        this.head = null;
    }

    public void add(int data) {
        Node newNode = new Node(data); // head부터 시작해서 .next가 null일 때 해당 주소를 넣을 것이다.

        // 처음 노드가 없을 때 setting
        if (head == null) {
            head = newNode;
            return;
        }

        // tmp라는 Node에 임시적으로 head 주소를 넣어서 .next가 null일 때 까지 계속 주소값을 덮어 쓸 것이다.
        Node tmp = head;
        // node객체의 .next가 null일 때까지 .next에 저장되어있는 node객체주소로 tmp주소를 변경
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        // tmp 참조변수 안에는 실제 Node 객체의 주소가 들어있다. 그래서 tmp.next에 값을 넣어주면 실제 객체의 .next 값이 변한다.
        tmp.next = newNode;
    }

    Node get(int index) {
        Node curr = head;
        if (index == 0) {
//            System.out.println("curr = " + curr);
            return curr;
        }
        for (int i = 1; i <= index; i++) {
            curr = curr.next;
        }
//        System.out.println("curr = " + curr);
        return curr;
    }

}

 

• TDD

class LinkedListTest {
    boolean LinkedListImpl(int a, int b) {
        LinkedList list = new LinkedList();

        // list 개수 추가
        for (int i = 0; i < a; i++) {
            list.add(i);
        }
        // 5번째 Node의 toString 값
        // Linked되어있지 않으면 예외가 터진다. Linked되어있으면 true 반환
        // a>=b인 경우만 true, - 마지막 Node의 next가 null이기 때문
        for (int i = 0; i < b; i++) {
            list.get(i);
        }
        return true;
    }

    @Test
    void addCorrect() {
        assertTrue(LinkedListImpl(8, 4));
        assertTrue(LinkedListImpl(8, 8));
        assertTrue(LinkedListImpl(8, 1));
        assertTrue(LinkedListImpl(1, 1));
        // True인 이유는 마지막 노드는 null 다음 Node로 연결하기 때문
        assertTrue(LinkedListImpl(7, 8));
    }
    @Test
    void addOverNum(){
        assertThrows(NullPointerException.class, () -> LinkedListImpl(1, 8));
        assertThrows(NullPointerException.class, () -> LinkedListImpl(6, 8));
    }
}

 

2. CircleLinkedList

• 구현

class LinkedList {
    private Node head;
    private Node tail;

    public LinkedList() {
        this.head = null;
    }

    public void add(int data) {
        Node newNode = new Node(data); // head부터 시작해서 .next가 null일 때 해당 주소를 넣을 것이다.

        // 처음 노드가 없을 때 setting
        if (head == null) {
            head = newNode;       //  동일 Node 객체 주소가짐
            tail = newNode;       //  동일 Node 객체 주소가짐
            newNode.next = head;  // .next에 처음 Node 주소 저장
        }else {
            tail.next = newNode; // tail.next에 새로운 Node 객체 주소로 변경 -> tail과 head는 같은 주소를 가지므로 head.next값도 변경됨
            tail = newNode;      // tail과 연결된 객체 주소를 최신 것으로 변경
            tail.next = head;    // 변경된 객체의 .next는 현재 null인 상태 -> 다시 처음 객체 주소인 head와 연결시켜서 circle 만듬
        }
    }

 

• TDD

class LinkedListTest {
    boolean LinkedListImpl(int a, int b) {
        LinkedList list = new LinkedList();

        // list 개수 추가
        for (int i = 0; i < a; i++) {
            list.add(i);
        }
        for (int i = 0; i < b; i++) {
            list.get(i);
        }
        return true;
    }

    @Test
    // linked 끝이 처음과 연결되어서 a < b 여도 정상 작동
    void addOverNumCircle() {
        assertTrue(LinkedListImpl(1, 8));
        assertTrue(LinkedListImpl(6, 8));
    }
}

 

3. DoubleLinkedList

• 구현

class Node {
    int data;
    Node next;
    Node prev;

    public Node(int data) {
        this.data = data;
	@@ -32,11 +33,10 @@ public void add(int data) {
        if (head == null) {
            head = newNode;       //  동일 Node 객체 주소가짐
            tail = newNode;       //  동일 Node 객체 주소가짐
        }else {
            tail.next = newNode; // tail.next에 새로운 Node 객체 주소로 변경 -> tail과 head는 같은 주소를 가지므로 head.next값도 변경됨
            newNode.prev = head;    // 변경된 객체의 .next는 현재 null인 상태 -> 다시 처음 객체 주소인 head와 연결시켜서 circle 만듬
            tail = newNode;      // tail과 연결된 객체 주소를 최신 것으로 변경
        }
    }

    Node get(int index) {
        Node curr = head;
        if (index == 0) {
            return curr;
        }
        for (int i = 1; i <= index; i++) {
            curr = curr.next;
        }
        return curr;
    }
}

 

• TDD

class LinkedListTest {
    boolean LinkedListImpl(int a, int b) {
        LinkedList list = new LinkedList();
        // list 개수 추가
        for (int i = 0; i < a; i++) {
            list.add(i);
        }
        for (int i = 0; i < b; i++) {
            list.get(i);
        }
        // 내림차순 생성
        for (int i = b; i < 0; i--) {
            list.get(i);
        }

        return true;
    }

    @Test
    void addCorrect() {
        assertTrue(LinkedListImpl(8, 4));
        assertTrue(LinkedListImpl(8, 8));
        assertTrue(LinkedListImpl(8, 1));
        assertTrue(LinkedListImpl(1, 1));
        assertTrue(LinkedListImpl(7, 8));
    }
    @Test
    void addOverNum(){
        assertThrows(NullPointerException.class, () -> LinkedListImpl(1, 8));
        assertThrows(NullPointerException.class, () -> LinkedListImpl(6, 8));
    }
}

 

4. CircleLinkedList

• 구현

 

public void add(int data) {
    Node newNode = new Node(data); // head부터 시작해서 .next가 null일 때 해당 주소를 넣을 것이다.

    // 처음 노드가 없을 때 setting
    if (head == null) {
        head = newNode;       //  동일 Node 객체 주소가짐
        tail = newNode;       //  동일 Node 객체 주소가짐
    }else {
        newNode.prev = tail;
        tail.next = newNode; // tail.next에 새로운 Node 객체 주소로 변경 -> tail과 head는 같은 주소를 가지므로 head.next값도 변경됨
        tail = newNode;      // tail과 연결된 객체 주소를 최신 것으로 변경
    }
    tail.next = head; // tail의 Node주소는 계속 newNode로 변경되고 next를 head 주소로 연결하므로 마지막 칸에서 다시 처음으로 돌아옴
    head.prev = tail; // 반대로 head의 이전Node 주소를 newNode로 연결하면 첫칸에서 마지막으로 잘 넘어감
}

 

• TDD

    @Test
    void addCorrect() {
        assertTrue(LinkedListImpl(8, 4));
        assertTrue(LinkedListImpl(8, 8));
        assertTrue(LinkedListImpl(8, 1));
        assertTrue(LinkedListImpl(1, 1));
        assertTrue(LinkedListImpl(7, 8));
    }

    @Test
    // linked 끝이 처음과 연결되어서 a < b 여도 정상 작동
    void addOverNumCircle() {
        assertTrue(LinkedListImpl(1, 8));
        assertTrue(LinkedListImpl(6, 8));
    }