단일 연결 리스트(Singly Linked List) 설명과 예제 코드(Java)

algorithm

링크드 리스트(Linked List, 연결 리스트)는 데이터들을 저장하기 위해 사용되는 데이터 구조입니다.

Singly Linked List는 데이터들이 한쪽 방향으로만 연결 되어있는 것을 말합니다. 데이터가 저장되는 객체를 node라고 하며, 가장 첫번째 node를 head라고 부릅니다.

이런 특성 때문에, 데이터 탐색 중에 한번 지나친 node를 찾으려면 다시 head부터 탐색을 해야 합니다.

위에서 설명한 내용을 그림으로 그려보면 다음과 같습니다. node는 value와 next 변수를 갖고 있습니다. value는 데이터가 저장되는 변수이고, next는 다음 index의 node를 가리키는 변수입니다. Singly Linked List

Singly Linked List를 코드로 표현하면 다음과 같습니다. 변수 val에 데이터가 저장되고, next는 다음 node를 가리킵니다.

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

Singly Linked List 구현하기

Singly Linked List를 코드로 구현해보면서 설명을 하겠습니다.

먼저 Singly Linked List 클래스는 다음과 같은 함수들을 제공합니다.

  • int get(int index) : 인자로 전달되는 index의 데이터를 리턴
  • void addAtHead(int val) : node를 리스트의 맨 앞에 추가
  • void addAtTail(int val) : node를 리스트 마지막에 추가
  • void addAtIndex(int index, int val) : 특정 index에 node를 추가
  • void deleteAtIndex(int index) : 특정 index의 node를 삭제

다음과 같이 위의 메소드들을 포함하는 MyLinkedList라는 클래스를 만들었습니다. 지금은 메소드만 정의되어있고, 메소드 내부의 코드는 구현되지 않았습니다.

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) {
    }
}

위의 코드는 Leetcode - Singly Linked List에서 가져왔습니다.

Leetcode에서 자신이 구현한 코드를 여러 테스트 케이스로 검증할 수 있습니다. 모든 테스트 케이스를 통과할 때까지 직접 구현해보세요.

구현된 코드를 먼저 보시려면 GitHub - SinglyLinkedList에서 확인하시면 됩니다.

addAtHead() : 맨 앞에 node 추가

맨 앞에 node를 추가하는 것은 어렵지 않습니다.

아래와 같이 head로 시작하는 링크드 리스트가 있을 때, node를 생성합니다. Singly Linked List - add at head

새로운 node가 head를 가리키도록 변경하면, 다음과 같은 모습이 됩니다. Singly Linked List - add at head

마지막으로 head가 node를 가리키도록 변경하면, 맨 앞에 노드가 추가된 것처럼 됩니다. Singly Linked List - add at head

다음은 위의 내용들을 코드로 구현한 것입니다.

/* Add a node of value val before the first element of the linked list.
 * After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
    if (head == null) {
        head = new SinglyLinkedNode(val);
        return;
    }

    SinglyLinkedNode node = new SinglyLinkedNode(val);
    node.next = head;
    head = node;
}

다음 케이스에 대해서 예외처리가 필요합니다.

  • head가 null일 때(node가 하나도 등록되지 않은 상태), head에 새로운 node를 등록

get(index) : index의 데이터를 리턴

get()은 인자로 전달된 index의 데이터를 리턴하는 메소드입니다.

먼저 next를 이용하여 특정 index의 node로 이동하고, 그 node의 데이터를 리턴하면 됩니다.

다음은 위에서 말한 내용을 코드로 구현한 것입니다.

/** Get the value of the index-th node in the linked list.
 * If the index is invalid, return -1. */
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;
        }
        // Move to Index (i + 1)
        cur = cur.next;
    }
    return cur.val;
}

다음 케이스들에 대해서 예외처리가 필요합니다.

  • head가 null일 때(node가 등록되지 않았을 때) -1을 리턴
  • node 개수보다 index가 더 클 때, -1을 리턴

addAtTail(val) : node를 마지막에 추가

리스트의 마지막에 node를 추가하는 것도 어렵지 않습니다.

리스트의 마지막 node를 먼저 찾고, 마지막 node가 생성한 node를 가리키도록 설정하면 됩니다.

다음 그림과 같이 head로 시작하는 리스트가 있고, 먼저 추가할 node를 생성합니다. Singly Linked List - add at head

그리고 리스트의 마지막 node가 생성한 node를 가리키도록 설정하면 됩니다. Singly Linked List - add at head

다음은 위에서 말한 내용을 코드로 구현한 것입니다.

/** Append a node of value val to the last element of the linked list. */
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;
}

다음 케이스에 대해서 예외처리가 필요합니다.

  • head가 null인 경우, head가 새로운 node를 가리키도록 설정

addAtIndex(index, val) : index에 node를 추가

addAtIndex()는 인자로 전달된 index에 node를 추가하는 메소드입니다.

특정 index의 node를 찾고, 그 위치에 node를 추가하며 됩니다.

먼저 다음 그림과 같이 리스트가 있을 때, 특정 index의 node(cur)와 그 이전 node(prev)를 찾습니다. 그리고 새로운 node를 생성합니다. Singly Linked List - add at index

prev가 새로운 node를 가리키고, 새로운 node가 cur를 가리키도록 변경하면 됩니다. Singly Linked List - add at index

다음은 위의 내용을 코드로 구현한 것입니다.

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list,
 * the node will be appended to the end of linked list.
 * If index is greater than the length, the node will not be inserted. */
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;
    }
}

다음 케이스들에 대해서 예외처리가 필요합니다.

  • head가 null일 때 index 0은 node 추가, 그 외의 index는 node를 추가하지 않습니다.
  • index가 리스트 길이와 동일한 값이라면, node를 마지막에 추가할 수 있습니다. 하지만 리스트 길이보다 크다면 아무것도 추가하지 않습니다.

deleteAtIndex(index) : index의 node를 삭제

deleteAtIndex()는 특정 index의 node를 삭제하는 것입니다. addAtIndex()와 비슷한 방식으로 구현하면 됩니다.

먼저 index의 node(cur)와, 그 node의 이전 node(prev)를 찾습니다. Singly Linked List - delete at index

그리고 prev가 cur의 다음 node를 가리키도록 변경하면 됩니다. Singly Linked List - delete at index

다음은 위의 내용을 코드로 구현한 것입니다.

/** Delete the index-th node in the linked list, if the index is valid. */
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;
    }
}

다음 케이스에 대해서 예외처리가 필요합니다.

  • head가 null인 경우, 아무것도 삭제하지 않습니다.
  • index 0을 삭제하는 경우(prev가 null), head는 head 다음의 node를 가리키도록 변경합니다.

전체 코드

완성된 코드는 GitHub - SinglyLinkedList에서 확인할 수 있습니다.

검증(Verification)

먼저 자신이 구현한 코드가 아래와 같은 간단한 테스트 케이스를 통과하는지 확인할 수 있습니다.

MyLinkedList3 linkedList = new MyLinkedList3();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3

System.out.println(linkedList.get(1)); // returns 2

linkedList.deleteAtIndex(1); // now the linked list is 1->3

System.out.println(linkedList.get(1)); // returns 3

다음과 같이 출력되면 이 테스트 케이스는 패스한 것입니다.

2
3

그리고 Leetcode - Singly Linked List에서 더 많은 테스트 케이스로 검증할 수 있습니다.

사이트에 자신의 코드를 붙여넣고 submit 버튼을 누르면 테스트 결과를 보여줍니다.

Leetcode - Singly Linked List

참고

Loading script...
codechachaCopyright ©2019 codechacha