리스트 (선형 리스트, 연결 리스트)

• 리스트란?

 리스트는 데이터를 순서대로 나열해 놓은 자료구조를 말한다. 리스트는 선형 리스트와 연결 리스트로 나눌 수 있는데 선형 리스트는 데이터들이 메모리에서 배열처럼 연속적으로 저장되어있는 리스트를 말하고 연결리스트는 각각의 데이터들이 메모리에 연속적으로 저장되어 있지는 않지만 각각의 데이터 안에 다음 순서의 데이터의 위치가 저장되어있는 리스트이다.

 

• 선형 리스트 구현

 선형 리스트는 배열과 같은 구조이기 때문에 1차원 배열을 통해 쉽게 구현할 수 있다. 

class Student{
    String name;
    int no;
    Student(String s, int n)
    {
        name = s;
        no = n;
    }
}
class Main {
    public static void main(String[] args) throws IOException {
        Student[] lst = new Student[7];
        lst[0] = new Student("seonjo", 0);
        lst[1] = new Student("jiko", 0);
        lst[2] = new Student("michang", 0);
        lst[3] = new Student("sumjo", 0);
        lst[4] = new Student("miyu", 0);
        lst[5] = new Student("yeomin", 0);
    }
}

실제로 그냥 배열이라고 생각해도 큰 문제는 없다. 하지만 배열과 다른점은 lst[1]에 새로 데이터를 추가한다면 원래 있던 lst[1]부터 그 뒤의 데이터들의 index를 1씩 뒤로 밀어야한다. 그리고 만약 lst[3]의 값을 삭제한다면 lst[4], lst[5]와 같이 뒤에있던 값들의 index는 1씩 앞으로 당겨져야한다. 이렇게 배열로 쉽게 구현할 수 있지만 선형 리스트의 기능을 구현하려면 비효율 적이다.

 

• 연결 리스트 구현

연결 리스트는 선형 리스트와 다르게 포인터를 이용해 구현한다. 포인터를 class Node<E>를 이용하여 구현을 할 건데 Node란 리스트에 있는 개별 요소를 뜻한다. 맨 앞의 노드는 data를 갖고 있고 그리고 다음 노드를 가리키는 포인터인 next를 갖고있다. 따라서 그 다음 노드를 확인할 수 있고 이렇게 쭉 가다보면 마지막 노드가 나오고 마지막 노드는 data와 다음 노드를 가리키는 포인터인 next를 갖고있는데 이때 next가 null이 된다. 대충 개념을 봤으니 코드를 보고 이해해보자.

class LinkedList<E>{
    class Node<E>{
        private E data;
        private Node<E> next;

        Node(E data, Node<E> next){
            this.data = data;
            this.next = next;
        }
    }
    private Node<E> head;

    public LinkedList(){
        head = null;
    }
}
class Main {
    public static void main(String[] args) throws IOException {
        LinkedList<Integer> lst = new LinkedList<>();
    }
}

 다음과 같이 LinkedList 클래스 내부에 Node라는 내부클래스를 만들어 data와 next를 포함하게 만든다. 안에 보면 head라는 노드의 포인터가 보이는데 head는 연결리스트의 맨 처음 노드의 포인터를 가리키는 것이다. LinkedList의 생성자를 보면 처음엔 노드가 없으므로 head가 null을 가리킨다.

 

 그러면 이 LinkedList를 사용하면서 같이 쓰는 함수들도 구현해보자.

 

(1) indexOf

먼저 연결 리스트 내에 매개변수로 주어진 data의 값이 존재하면 그 data의 index를 아니면 -1을 반환하는 indexOf함수이다.

public int indexOf(E data){
    Node<E> ptr = head;
    int index = 0;
    while (ptr != null)
    {
        if (ptr.data == data)
            return index;
        ptr = ptr.next;
        index++;
    }
    return -1;
}

간단하게 head노드부터 시작하여 data와 ptr의 data를 비교하며 다르면 다음 노드로 넘어가고 data와 같은 data를 갖는 노드가 없는경우 -1을 반환한다. 

 

 

(2) addFirst

 두번째로 맨 앞에 노드를 추가하는 addFirst함수이다. 이는 노드를 추가하는 것 뿐 아니라 head노드를 가리키는 Node의 포인터 head의 값을 새로 추가하는 노드로 바꿔야한다.

public void addFirst(E data)
{
    Node<E> ptr = head;
    Node<E> new_Node = new Node<>(data, ptr);
    head = new_Node;
}

간단하게 원래있던 head노드의 포인터를 ptr에 저장해 새로 만드는 노드의 next값으로 넣어주고 head가 새로 만든 노드를 가리키게 하면 된다.

 

 

(3) addLast

 맨 앞에 노드를 추가하는 addFIrst와 달리 맨 뒤에 꼬리 노드를 새로 추가하는 함수이다. (가장 마지막 노드를 꼬리노드라 함) head부터 시작해서 꼬리노드를 찾고 그 뒤에 새로운 노드를 붙여주면 된다.

public void addLast(E data)
{
    Node<E> ptr = head;
    if (ptr == null)
        addFirst(data);
    while (ptr.next == null)
        ptr = ptr.next;
    ptr.next = new Node<>(data, null);
}

여기서 중요한 점은 연결 리스트에 노드가 1개도 없어서 head가 null인 경우 while 문에 들어가면 오류가 나기 때문에 addFirst를 사용하여 따로 예외처리를 해준다. (리스트 안에 노드가 없으므로 마지막에 노드를 추가하는게 맨 앞에 노드를 추가하는 거랑 같은 개념이기 때문에 가능)

 

 

(4) add

 add는 data를 이용해 만든 노드를 연결 리스트의 원하는 index에 삽입하는 함수이다. index가 0이면 addFirst를 이용해 따로 처리해주고 나머지 경우에는 새로 추가할 노드의 next를 index에 위치한 노드로 바꿔주고 새로 추가한 노드를 index - 1에 위치한 노드의 next로 해주는 것이다.

public void add(int index, E data)
{
    if (index == 0)
        addFirst(data);
    else {
        int i = 0;
        Node<E> ptr = head;
        while (i != index - 1)
        {
            ptr = ptr.next;
            i++;
            if (ptr.next == null)
                break;
        }
        Node<E> new_Node = new Node<>(data, ptr.next);
        ptr.next = new_Node;
    }
}

 다음과 같이 while문을 통해 head노드에서 부터 index - 1의 노드를 찾고 위에서 말한 내용을 처리해준다. 이때 만약 매개변수로 들어온 index까지 가기전에 ptr.next가 null이 나온다면(꼬리 노드가 등장) new_Node는 맨 마지막에 삽입해준다.

 

 

(5) removeFirst

이 함수는 맨 앞에 있는 노드, 즉 head노드를 삭제하는 함수이다. head노드를 삭제하면 그 다음 노드가 head노드가 되기 때문에 head지정도 놓치면 안되는 부분이다.

public void removeFirst()
{
    if (head != null)
        head = head.next;
}

if문은 head가 null을 가리키면 삭제할 노드가 없기 때문에 작성한 조건문이다.

 

 

(6) removeLast

 이 함수는 맨 뒤에 있는 노드, 즉 꼬리노드를 삭제하는 함수이다. addLast때처럼 head에서 꼬리노드의 앞쪽 노드까지 while문을 통해 이동하고 꼬리노드의 앞쪽 노드의 next를 null로 바꿔주면 된다.

public void removeLast()
{
    if (head != null) {
        if (head.next == null)
            removeFirst();
        else {
            Node<E> ptr = head;
            Node<E> ptr_next = head.next;
            while (ptr_next.next != null) {
                ptr = ptr_next;
                ptr_next = ptr_next.next;
            }
            ptr.next = null;
        }
    }
}

while문의 조건에서 ptr의 next의 next를 참조하기 때문에 먼저 if문으로 head와 head의 next가 null인 경우를 따로 예외처리 해주었다. head가 null이면 삭제할 노드가 없어서 아무것도 안하고 종료이고 head의 next가 null인 경우는 삭제할 노드가 맨 앞의 노드이기 때문에 removeFirst를 이용해서 삭제했다. 그 뒤는 next의 next가 null인 경우를 찾아서 next를 null로 바꿔 꼬리노드와의 연결을 삭제한다.

 

 

(7) remove

 이번에는 원하는 index의 노드를 삭제하는 함수를 보자. add때와 똑같이 index - 1의 노드를 찾고 index - 1의 노드의 next를 index + 1의 노드로 바꿔주면 된다. 만약 index == 0이면 removeFirst를 사용한다.

public void remove(int index)
{
    if (index == 0)
        removeFirst();
    else
    {
        Node<E> ptr = head;
        int i = 0;
        while (i != index - 1)
        {
            ptr = ptr.next;
            i++;
            if (ptr.next.next == null)
                break;
        }
        ptr.next = ptr.next.next;
    }
}

만약 while문에서 ptr.next.next가 null인 경우 ptr이 ptr.next를 한 경우 ptr.next.next를 했을때 오류가 나기 때문에 break를 해줘야한다. 그것 말고는 앞에서 봤던 노드를 삭제하는 내용과 add에서 원하는 index에 접근하는 내용 등 익숙한 내용을 적용한다.

 

 

(8) size

 마지막으로 연결 리스트의 크기를 반환하는 함수 size이다. 사실 head처럼 LinkedList class의 클래스 변수로 size를 설정해 add시 size++을 하고 remove시 size--를 하여 크기를 기록해도 된다. 하지만 이번에는 직접 크기를 구하는 코드를 짜 보았다.

public int size()
{
    int size = 0;
    Node<E> ptr = head;
    while (ptr != null)
    {
        ptr = ptr.next;
        size++;
    }
    return (size);
}

다음과 같이 size를 0으로 지정해놓고 head에서 null까지 방문하면서 size를 +1씩해주는 간단한 함수이다.