자료구조 (SinglyLinkedList 실습예제)

SinglyLinkedList 실습

• 단일 연결 리스트를 개념 정리했던 대로 추가해보자
• 예제는 https://leetcode.com/explore/learn/card/linked-list/209/singly-linked-list/ 을 참고 하였다.
• 먼저 노드의 정보를 가지고 있는 클래스를 생성한다.

public class SinglyLinkedNode { 
    int val;
    SinglyLinkedNode next = null; 
    SinglyLinkedNode(int v){
    val = v; 
    }
   }

• 다음으로 예제로 구현해볼 메소드를 작성한다

    public class MyLinkedList {

    private SinglyLinkedNode head = null;

    public MyLinkedList() {
    }

    public int get(int index) {
    }

    public void addAtHead(int val) {
    }

    public void addAtTail(int val) {
    }

    public void addAtIndex(int index, int val) {
    }

    public void deleteAtIndex(int index) {
    }

• 먼저 get(index) 메서드로 데이터 리턴하는 코드를 만든다

public int get(int index) {  
if (head == null) {  
return -1;  
}  
SinglyLinkedNode cur = head;  
for (int i = 0; i < index; i++) {  
if (cur.next == null) {  
return -1;  
}  
cur = cur.next;  
}  
return cur.val;  
}

• 맨 앞 노드 추가하는 과정을 코드로 구현 해본다.

public void addAtHead(int val) {  
if (head == null) {  
head = new SinglyLinkedNode(val);  
return;  
}  
SinglyLinkedNode node = new SinglyLinkedNode(val);  
node.next = head;  
head = node;  
}

• 맨 뒤에 노드를 추가하는 과정을 코드로 구현

public void addAtTail(int val) {  
if (head == null) {  
head = new SinglyLinkedNode(val);  
return;  
}

    SinglyLinkedNode cur = head;
    while (cur.next != null) {
        cur = cur.next;
    }
    SinglyLinkedNode node = new SinglyLinkedNode(val);
    cur.next = node;
}

• 중간에 노드를 삽입하는 과정을 코드로 구현

public void addAtIndex(int index, int val) {  
if (head == null) {  
if (index == 0) {  
head = new SinglyLinkedNode(val);  
}  
return;  
}

    SinglyLinkedNode prev = null;
    SinglyLinkedNode cur = head;
    for (int i = 0; i < index; i++) {
        if (cur == null) {
            return;
        }
        //Move to index(i+1)
        prev = cur;
        cur = cur.next;
    }
    SinglyLinkedNode node = new SinglyLinkedNode(val);
    if (prev == null) {
        node.next = head;
        head = node;
    } else if (cur == null) {
        cur = node;
        prev.next = cur;
    } else {
        prev.next = node;
        node.next = cur;
    }
}

• 중간 노드를 삭제하는 과정을 코드로 구현
  (맨 앞이나 맨 뒤에 노드 삭제 과정은 생략했다.)

public void deleteAtIndex(int index) {  
if (head == null) {  
return;  
}

    SinglyLinkedNode prev = null;
    SinglyLinkedNode cur = head;
    for (int i = 0; i < index; i++) {
        if (cur.next == null) {
            return;
        }
        // Move to Index (i +1)
        prev = cur;
        cur = cur.next;
    }

    SinglyLinkedNode next = cur.next;
    if (prev == null) {
        head = head.next;
    } else if (next == null) {
        prev.next = null;
    } else {
        prev.next = next;
    }

• 과정을 잘 이해하면서 전체적으로 몇번 익히는 공부법을 진행하고 있다.