[Java] 연결 리스트

1. 리스트

 

순서를 가진 데이터의 집합을 가리키는 추상자료형.

 

값의 중복을 허용한다.

 

• 순차 리스트
  : 배열을 기반으로 구현.
  : Random access 가능.
  : 삽입/삭제 연산에 불리.
• 연결 리스트
  : 메모리의 동적할당을 기반으로 구현.
  : 삽입/삭제에 유리.
  : 탐색에 불리.

 

---

2. 연결 리스트

 

• 자료의 논리적인 순서와 물리적인 순서가 일치하지 않을 수 있다.
• 개별적인 노드를 연결하여 하나의 자료구조를 형성.

 

class Node<T> {
    T data';
    Node<T> link;
}

• node
  • 데이터 필드
  • 링크 필드 : 연결된 노드의 참조값을 저장.
• head
  • 첫번째 노드에 대한 참조값을 가지고 있음.
• tail
  • 마지막 노드에 대한 참조값을 가지고 있음.

 

---

가. 단순 연결 리스트

 

 

다음 노드에 대한 참조값만 가지고 있음.

 

1) 단순 연결 리스트 응용 - Stack

public class MyNode<T> {

    public T data;
    public MyNode<T> link;


    public MyNode(T data, MyNode<T> link) {
        super();
        this.data = data;
        this.link = link;
    }

    @Override
    public String toString() {
        return "MyNode [data=" + data + ", link=" + link + "]";
    }

}

public interface IStack<E> {
    void push(E e);
    E pop();
    E peek();
    boolean isEmpty();
    int size();
}

import java.util.EmptyStackException;

public class MyStack<E> implements IStack<E> {

    private MyNode<E> top;
    private int cnt;

    @Override
    public void push(E e) {
        top = new MyNode<E>(e, top);
        cnt++;
    }

    @Override
    public E pop() {
        if(this.isEmpty()) {
            throw new EmptyStackException();
        }
        MyNode<E> tmp = top;
        top = top.link;
        tmp.link = null;
        cnt--;
        return tmp.data;
    }

    @Override
    public E peek() {
        if(this.isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    @Override
    public boolean isEmpty() {
        return top==null;
    }

    @Override
    public int size() {
        return cnt;

//        int count = 0;
//        for(MyNode<E> node = top; node != null; node=node.link) {
//            count++;
//        }
//        return count;

    }

}

public class MyStackTest {

    public static void main(String[] args) {
        IStack<String> stack = new MyStack<>();

        stack.push("감장탕");
        stack.push("짬뽕");
        stack.push("짜장면");
        stack.push("돈까스");
        stack.push("소고기");

        System.out.println(stack.peek());
        System.out.println(stack.size());
        System.out.println(stack.pop());
        System.out.println(stack.size());

        while(!stack.isEmpty()) {
            System.out.println(stack.pop());
            System.out.println(stack.size());
        }
        System.out.println(stack.isEmpty());
    }

}

스택은 한쪽 끝에서만 삽입/삭제가 발생하므로 단순 연결 리스트로도 충분히 구현할 수 있다.

 

 

단순 연결 리스트로 스택을 구현할 때 top으로 1번 자리가 2번보다 더 적합하다.

 

스택을 구현함에 있어서 2번을 탑으로 선택하면 추가적인 탐색 발생한다.

 

삽입, 삭제 시 앞선 노드를 찾기 위해서 모든 노드를 탐색해야 하기 때문이다.

 

하지만 1번을 탑으로 사용하면 head로 탐색없이 바로 접근 가능할 수 있기 때문이다.

 

---

나. 이중 연결 리스트

 

 

앞, 뒤 노드에 대한 참조값을 가지고 있음.

 

양방향 탐색이 가능하다.

 

---

다. 원형 연결 리스트

 

 

처음과 끝이 연결된다.

 

어떤 지점임의의 지점에서 탐색을 시작해도 모든 노드를 탐색할 수 있다.

 

---

 

[C++] Linked list