[자료구조] Single Linked List

Single Linked List

Linked List는 많은 양의 자료이동이 필요할때 사용하는 자료구조이다. Linked List는 Node라는 단일된 객체들의 연결로 표현한다. 오늘 포스팅에서 소개할 Single Linked List는 이러한 연결이 한개로 순차적인 표현을 한다.

 

Single Linked List 설계

단일 연결 리스트의 설계를 해보자

Node 설계

Node는 데이터가 담기는 핵심적인 요소이다. 일반적인 배열로 생각하면 [1,2,4]같이 있다면 "1", "2"같은 단일된 요소 해당 인덱스의 요소를 가리키는 것이다.
그렇다면 Node는 데이터를 저장해야하는 Data변수가 있어야 된다. 그리고 연결을 표현해야함으로 다음 Node로 가는 Pointer가 있어야겠다.

그림으로 표현하면 다음 처럼 표현 할 수 있겠다.

그림처럼 data부분과 다음 노드를 가르키는 pointer부분을 코드로 작성해보자

class Node
{
    int data;
    Node next;

    //생성자
    public Node(int data)
    {
        this.data = data;
        next = null;
    }
}

data부분은 int로 설정했다. 그리고 다음 노드를 가르키는 pointer로 Node클래스 변수를 선언하여 next라는 이름으로 선언해주었다.
생성자로는 data인자를 받으면 그것을 멤버변수인 data에 대입시키고 일단 다음 Node의 next변수는 null로 초기화 해준다.
다음처럼 간단하게 Node를 설계해보았다.

Linked List 설계

이제 실질적으로 삽입, 삭제, 검색, 출력등 여러 메소드를 구현해야하는 Linked List 클래스를 설계해보자

우선 선언해야 하는 멤버 변수를 고려해보자
Linked List의 첫 요소에 접근할 수 있는 pointer 변수가 있어야 겠다.
그 외는 코드를 작성하면서 추가해보도록 하자

다음은 선언해야하는 메소드를 고려해보자
우선 삽입,삭제와 검색는 물론이고 그 밖에 출력을 위한 show() 메소드 정도만 있으면 되겠다.

위 내용을 아래 코드로 작성해보았다. 스켈레톤 코드로 내용을 추가해야한다.

class LinkedList
{
    private int len; // Linked List의 길이를 저장
    private Node head; // 첫 요소를 가리키는 pointer 변수

    public LinkedList(int len) {} //생성자
    public int length() {}; //멤버 변수 len 반환
    public void insert(int data) {} //데이터 삽입
    public void delete(int data) {} //데이터 삭제
    public int search(int data) {} //데이터 검색(위치 반환(인덱스))
    public String toString() {} // toString 메소드 오버라이드
    public void print() {} // Linked List 출력

    private boolean isEmpty() {} //Linked List의 비어있는지에 대한 여부
}

생성자 & 기타 메소드

우선 생성자를 살펴보자 생성자는 간단하게 멤버변수인 len과 head를 초기화 주면 된다.

public LinkedList()
{
    len = 0;
    head = null;
}

다음은 Linked List가 비어있는지 여부에 대한 isEmpty메소드이다.

private boolean isEmpty() {return head == null && len == 0;}

정말 간단하게 한줄로 구현가능하다. head가 null이고 길이가 len이면 비어있는 것이니 직관적이다.

삽입

삽입은 첫 요소(head)에서 마지막 요소까지 이동한 다음 마지막 요소(Node)의 next변수를 새로 추가하는 Node로 바꿔주면 된다. 여기서 중요한 것은 head에서 부터 다음 노드로 계속해서 이동하는 것이다.

경우의 수는 2가지이다.
1. Linked List가 비어있는가
2. Linked List가 비어있지 않는가.

코드를 살펴보자

public void insert(int data)
{
    if(this.isEmpty()) {head = new Node(data);} //비어있는 경우 head에 새로운 Node를 삽입한다.
    else
    {
        Node p = head; //노드 p를 마지막 노드로 이동 시킨다.

        //p의 next가 null이 될때까지 반복
        //p=p.next는 다음 노드로 이동을 표현
        while(p.next != null) {p = p.next;}

        p.next = new Node(data); //마지막 노드에서 새로운 Node 추가
    }
    len++;
}

삽입 메소드에서 중요한 것은(삭제, 검색에서도 마찬가지다.) Node의 이동이다.
while문을 통해 head에서 마지막 노드까지 이동시킨 것을 주목하자.

삭제

삭제또한 삽입과 마찬가지고 while을 통한 Node의 이동을 이용해 삭제를 구현한다.
또한 삭제에서는 삭제할 노드의 좌우의 연결을 구현해야하는데, 여기선 pointer변수를 2개를 사용한다.
그림을 통해 살펴보자

그림에서 처럼 1024를 삭제할때, 2개의 포인터(q,p)를 이용해서 q의 next를 p의 next로 변경하면서 삭제를 구현한다.
즉 기존의 Node의 연결을 끊고 새로운 연결을 만들어서 삭제를 구현한 것

코드를 살펴보자

public void delete(int data)
{
    Node q=null, p=head;

    if(this.isEmpty()) {System.out.println("List is Empty");}
    else if(head.data == data) {head = head.next;}
    else
    {
        // p의 next가 null이거나 p의 data가 원하는 data일때까지 반복
        while(p.next != null && p.data != data) {q=p; p = p.next;}

        if(p.next != null) {q.next = p.next;}
        else {System.out.println("Not found");}
    }
    p = null;
    len--;
}

삭제할 노드가 head일 경우와 아닐 경우로 나눠서 처리하였다.

검색

마지막으로 검색 알고리즘이다. 검색은 해당하는 data의 위치(인덱스)를 반환하도록 설계하였는데 이 또한 while 반복을 통해 해당하는 Node를 탐색하는 알고리즘을 사용하였다.

바로 코드를 확인해보자

public int search(int data)
{
    Node p=head;
    int idx = 0; //반환할 인덱스 변수

    if(this.isEmpty()) {return -1;}
    else if(head.data == data) {return 0;}
    else
    {
        // p가 null이거나 p의 데이터가 찾고자하는 데이터일때 까지 반복
        while(p != null && p.data != data) {p = p.next; idx++;}

        if(p != null) {return idx;}
        else {System.out.println("Not found"); return -1;}
    }
}

delete 메소드와 상당히 유사하다 따라서 설명을 조금 생략하려한다.

전체 코드

전체 코드는 아래 github 링크에서 자세히 확인해 볼수 있다.
https://github.com/JoSangYeon/Algorithm/blob/master/LinkedList/Linked.java

main을 제외한 코드는 아래이다.

class Node
{
    int data;
    Node next;
    public Node(int data)
    {
        this.data = data;
        next = null;
    }
}

class LinkedList
{
    private int len;
    private Node head;

    public LinkedList()
    {
        len = 0;
        head = null;
    }

    public int length() {return this.len;}

    public void insert(int data)
    {
        if(this.isEmpty()) {head = new Node(data);}
        else
        {
            Node p = head;
            while(p.next != null) {p = p.next;}
            p.next = new Node(data);
        }
        len++;
    }
    public void delete(int data)
    {
        Node q=null, p=head;

        if(this.isEmpty()) {System.out.println("List is Empty");}
        else if(head.data == data) {head = head.next;}
        else
        {
            while(p.next != null && p.data != data) {q=p; p = p.next;}

            if(p.next != null) {q.next = p.next;}
            else {System.out.println("Not found");}
        }
        p = null;
        len--;
    }

    public int search(int data)
    {
        Node p=head;
        int idx = 0;

        if(this.isEmpty()) {return -1;}
        else if(head.data == data) {return 0;}
        else
        {
            while(p != null && p.data != data) {p = p.next; idx++;}

            if(p != null) {return idx;}
            else {System.out.println("Not found"); return -1;}
        }
    }

    public String toString()
    {
        String result= "[ ";

        Node p = head;
        while(p != null)
        {
            result += p.data+" "; 
            p = p.next;
        }
        result += "]";

        return result;
    }

    public void print() {System.out.println(this.toString());}

    private boolean isEmpty() {return head == null && len == 0;}
}

결론

Single Linked List는 (내 생각)자료구조에서 가장 기본적인 알고리즘인것 같다. 이를 통해 Linked Stack과 Queue등 여러가지를 만들 수 있다. 다만 Single Linked List의 아쉬운 점은 마지막 요소에 접근하기 위해 항상 head 노드를 거쳐 이동해야하는 단점이 있다. 이를 보완한 것이 Double Linked List로 좌우 Node에 대한 pointer 변수가 존재하는 Linked List가 있다. 다음 포스트는 아마 이 DLL이 되지 않을까 싶다.