자료구조 스터디 Week3 - 리스트

리스트는 '줄 세워져 있는 데이터' 또는 '죽 늘어선 데이터'를 의미한다.

리스트를 관리하기 위해 데이터를 추가 혹은 삭제가 가능하며, 값을 가져올 수도 있다. 리스트는 ADT 리스트로, 구현 방법은 명시하지 않고, 추상화를 통해 자료구조가 제공하는 기능들에 대해서만 명시하는 것을 말한다.

 

추상 데이터 타입에서 정의되는 핵심 기능은 크게 6가지로 볼 수 있다. - add, append, remove, removeItem, get, set

• add() - 특정 인덱스에 데이터 추가 ex) add(3, 250)
• append() - 리스트 끝에 데이터 추가
• remove() - 특정 인덱스의 요소를 제거
• removeItem() - 특정 값의 요소를 제거
• get() - 특정 인덱스 요소를 반환
• set() - 특정 인덱스 요소 값을 변경 ex) set(3, 250)

 

리스트는 크게 두 가지로 나눌 수 있다.

•  배열 리스트
•  연결 리스트

 

배열 리스트

배열 리스트는 시작 위치부터 빈 자리 없이 자료를 순서대로 연속적으로 저장하는 자료형이다.

주소를 할당 받고 인덱스를 통해 접근 및 추가 / 삭제가 가능하다.

 

 

 

메모리의 연속된 공간에서 데이터를 관리하기 때문에 초기화 과정에서 이름과 크기만 정하면 되므로 직관적이고 편리하다는 장점이 있다. 하지만 배열 크기를 초과하는 데이터가 할당될 경우, 더 큰 범위의 리스트에 값을 복사하여 붙여넣어야 하기 때문에 공간 낭비가 심하다는 단점이 있다.

 

배열 리스트의 필드는 2개, 원소들이 저장되는 배열 item[]과 원소의 총 수를 저장하는 numItems가 있다.

 

배열 리스트 작업

원소 삽입

 

위의 그림은 77을 리스트의 3번째 원소로 삽입하는 예시이다. 원소들이 배열 item[0...8] 인덱스에 각각 저장되어 있고, 3번째 인덱스에 값이 추가 된다면, 이후의 인덱스는 시프트 된다. 3번째 인덱스에 77이라는 요소가 들어오기 위해 오른쪽으로 한칸씩 시프트를 한 다음 값을 추가할 수 있다.

 

위의 알고리즘은 다음과 같다.

add(k, x):
    if (numItems >= item.length || k < 0 || k > numItems) {
    	// 에러
    }
    else {
    	for i <- numItems-1 to k:
        	item[i+1] <- item[i]	// 우시프트
        item[k] <- x
        numItems++
    }

 

마지막 인덱스부터 오른쪽으로 값을 시프트하여 원소 삽입 공간을 비울 수 있다.

 

위의 알고리즘에서 시간복잡도는 최소 O(1), 최악의 경우 O(n)을 따른다. 마지막 인덱스에 값을 추가해야 한다면, 시프트 필요 없이 값을 추가만 하면 되지만, 첫번째 인덱스에 값을 추가해야 할 경우 리스트 전체를 시프트 해야하는 단점이 있다.

그리고 만약에 numItems를 초과하는 인덱스를 전달받을 경우에는 에러를 출력하기 때문에 새로운 리스트를 만들어서 따로 메모리 공간을 할당해야하는 번거로움이 있다.

 

배열 리스트 구현(제네릭)

제네릭 형태로 작성하여 범용성도 보장하며, 강력한 타입 체크 기능도 갖출 수 있다.

public class ArrayList<E> implements ListInterface<E> {
    private E item[];
    private int numItems;
    private static final int DEFAULT_CAPACITY = 64; // 내부 배열의 초기 크기, 정적 바인딩
}

public ArrayList() {
	item = (E[]) new Object[DEFAULT_CAPACITY];
    numItems = 0;
}

public ArrayList(int n) {
	item (E[]) new Object[n];
    numItems = 0;
}

public void add(int index, E x) {
	if (numItems >= item.length || index < 0 || index > numItems) {
    	// 에러
    } else {
    	for (int i = numItems -1; i >= index; i--) {
        	item[i + 1] = item[i];
        }
        item[index] = x;
        numItems++;
    }
}

 

 

연결 리스트

연결리스트는 원소가 추가될 때마다 공간을 할당받아 추가하는 자료형이다.

 

 

연결리스트는 원소를 저장하는 필드 item과 다음 노드를 가리키는 필드 next로 구성되어 있다.

자바에서 next 필드는 링크(reference)를 나타낸다.

 

 

위의 이미지는 연결리스트의 기본 자료 형태이다. 첫 번째 노드를 가리키는 레퍼런스 head가 있다. 나머지 노드는 첫 번째 노드에서 링크를 따라 접근하며, 맨 마지막 노드 뒤에는 노드가 존재하지 않기 때문에 null 값을 할당한다. 노드는 각각 객체를 나타낸다고 볼 수 있다. 연결 리스트에서 각각의 노드는 다음 객체의 주소를 참조하면서 이어져있다.

 

연결 리스트 작업

아래 이미지는 원소 17과 35사이에 77을 삽입하는 예시이다. 배열 리스트와 다르게 시프트 없이 레퍼런스를 변경하여 간단하게 새 노드를 삽입할 수 있다.

 

 

또한 더미 헤드를 추가하게 되면 맨 앞에 원소를 추가할 때, 조건을 추가해야하는 번거로움을 덜 수 있다.

 

더미 헤드가 없을 경우 직전 노드인 head는 레퍼런스 값이 null로 존재하기 때문에 단일 코드로 작성하면 오류가 발생한다. 따라서 아래와 같이 두 가지 방식으로 나눠서 작성해야 한다.

if (k = 0) {
    newNode.item <- x
    newNode.next <- head
    head <- newNode
    numItems++
} else {
    newNode.item <- x
    newNode.next <- prevNode.next
    prevNode.next <- newNode
    numItems++
}

 

하지만 더미 헤드를 추가하게 되면 더미 헤드 노드가 직전 노드가 되어서 prevNode.next에 값을 할당할 수 있다.

newNode.item <- x
newNode.next <- prevNode.next
prevNode.next <- newNode
numItems++

 

연결 리스트 구현(제네릭)

public class LinkedList<e> implements ListInterface<E> {
    private Node<E> head;
    private int numItems;
    
    public LinkedList() {
        numItems = 0;
        head = new Node<>(null, null);
    }
    
    public void add(int index, E item) {
        if (index >= 0 && index <= numItems) {
            Node<E> prevNode = getNode(index - 1);
            Node<E> newNode = new Node<>(item, prevNode.next);
            prevNode.next = newNode;
            numItems++;
        }
    }
    
    public void append(E item) {
        Node<E> prevNode = head;
        while (prevNode.next != null) {
            prevNode = prevNode.next;
        }
        Node<E> newNode = new Node<>(item, null);
        prevNode.next = newNode;
        numItems++;
    }
}

 

배열 리스트 vs 연결 리스트

	배열 리스트	연결 리스트
크기	고정된 크기	원소에 따라 변경
공간의 연속성	O	X
탐색 시간	O(1)	최소 O(1), 최악 O(n)
필요 공간	작다	크다(추가 reference 때문)

 

원형 연결 리스트

연결 리스트의 탐색 시간이 최악의 경우 O(n)이 되는 단점을 보완한 리스트이다.

기존의 연결 리스트는 첫 노드에 바로 접근할 수 있는 반면에 마지막 노드는 링크를 끝까지 따라가야 접근할 수 있었고 총 O(n)의 시간이 들었다. 이 구조를 보완한 것이 바로 원형 연결 리스트이다.

 

레퍼런스 head가 더미 헤드 노드를 가리키도록 하는 대신 마지막 노드에 대한 레퍼런스 tail을 두고, 마지막 노드가 맨 앞의 더미 헤드 노드를 링크하고 있다. 따라서 원소를 삽입 / 삭제할 때 마지막 원소의 경우에도 O(1). 상수 시간이 드는 장점이 있다.

 

 

양방향 연결 리스트

기존의 리스트는 어떤 노드를 한번 지나면 따로 메모리를 할당하지 않는 이상 반대 방향으로 돌아갈 수 없다. 하지만 양방향 연결 리스트의 특정 노드는 다음 노드 뿐만 아니라 이전의 노드의 reference까지 포함하고 있기 때문에 앞뒤로 자유롭게 이동할 수 있다.

 

리스트의 마지막 원소의 next가 헤드 노드를 가리키고, 헤드 노드의 prev가 마지막 노드를 가리킨다.

https://inpa.tistory.com/entry/JAVA-%E2%98%95-LinkedList-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%99%84%EB%B2%BD-%EC%A0%95%EB%B3%B5%ED%95%98%EA%B8%B0