[자료구조] 04. 연결 리스트(Linked List)

연결 리스트(Linked List)

연결 리스트는 떨어진 공간에 있는 데이터들을 포인터를 이용하여 연결되어 있는 자료구조이다. 배열은 순차적으로 연결되어 있는 공간에 데이터를 넣는 자료구조여서 배열과는 다르다.

연결 리스트는 노드로 이루어져 있는데, 여기서 노드란 데이터와 포인터를 담고 있는 공간 단위이다.

포인터는 다음 노드의 주소 값을 저장하는 공간이다.

 

장점

• 미리 공간을 할당하지 않아도 됨

단점

• 연결을 위한 별도 공간이 필요하므로, 저장공간 효율이 좋지 않음
• 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
• 중간 데이터 삭제 시, 앞 뒤 노드의 연결을 재구성해야 하는 부가적인 작업이 필요

 

연결 리스트를 직접 구현해보며 장,단점을 살펴보고 시간 복잡도에 대해서도 알아보자

---

구현

IList 인터페이스를 생성하여 구현에 필요한 메서드를 아래와 같이 정의했다.

 

IList 인터페이스

public interface IList<E> {
	void add(E e);                 		   //데이터 추가

	void insert(int index, E e);   		   //index 위치에 데이터 추가

	void clear();				   		   //데이터 모두 삭제

	boolean delete(E e);		   		   //해당 데이터 삭제

	boolean deleteByIndex(int index);      //index 위치에 있는 데이터 삭제

	E get(int index);					   //index 위치에 있는 데이터 반환

	int indexOf(E e);					   //해당 데이터 index 반환

	boolean isEmpty();					   //리스트에 데이터가 있는지 없는지 반환

	int size();
}

 

해당 인터페이스를 implements하여 MyLinkedList 클래스를 생성하여 해당 클래스에 구현해보자.

 

MyLinkedList 클래스

public class MyLinkedList<E> implements IList<E> {
	private int size;
	private Node head;

	public MyLinkedList() {
		this.size = 0;
		this.head = new Node(null);
	}
    
	private class Node {
		E data;
		Node next;

		Node(E data) {
			this.data = data;
		}

		Node(E data, Node next) {
			this.data = data;
			this.next = next;
		}
	}
}

해당 소스를 보면 내장 클래스로 Node가 있는데 이것이 위에서 설명한 노드 역할을 해줄 클래스다.

위에서 설명했듯이 노드는 데이터와 다음 노드를 가리키는 포인터가 있다고 했다. 그래서 제네릭 타입으로 데이터를 담는 data 변수, 다음 노드와 연결할 Node 타입의 next 변수로 구성했다.

그리고 MyLinkedList 클래스에 2개의 필드가 있는데 하나는 해당 객체에 담긴 데이터의 갯수를 반환할 size, 시작 노드를 담을 head가 있다.

 

그 다음, 이제 인터페이스에서 정의한 추상 메서드들을 구현해보자.

 

 

add(E e) 메서드

 

연결 리스트에 처음 값을 추가할 때, 노드를 생성해서 head의 포인터에 생성한 노드를 연결해줘야 한다.

그 다음 값을 추가 한다면 전에 추가한 노드와 새로 생성한 노드를 연결해줘야 한다.

 

그래서 add 메서드를 아래와 같이 구현했다.

@Override
public void add(E e) {
    Node curr = this.head;

    while (curr.next != null) {
        curr = curr.next;
    }

    Node node = new Node(e);
    curr.next = node;
    size++;
}

curr에 head를 처음에 대입해주고, while을 통해 다음 노드가 null일 때까지 계속 노드들을 순회해준다. 그래서 curr에는 맨 마지막 노드가 대입될 것이다.

그다음 추가할 노드인 node 변수를 할당한다.

그리고 맨 마지막 노드의 포인터 역할인 next에 node를 넣어줌으로써 위의 그림과 같이 노드 간의 연결이 이루어진다.

(size++은 노드 추가됐음으로 증가)

 

 

insert(int index, E e) 메서드

중간에 노드를 추가한다면, 앞 뒤 노드를 재연결 해줘야 한다. 위의 그림을 보면 알 수 있듯이, 기존에 Prev와 Curr가 서로 연결되어 있다가 사이에 insert를 한다면 Prev의 다음 노드는 새로 추가된 노드가, 그리고 새로 추가된 노드의 다음 노드가 Curr로 변경되어야 한다는 것이다.

 

그래서 아래와 같이 구현했다.

@Override
public void insert(int index, E e) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException();

    Node prev = this.head;
    Node curr = prev.next;

    int i = 0;
    while (i++ < index) {
        prev = prev.next;
        curr = curr.next;
    }

    Node node = new Node(e, curr);
    prev.next = node;
    size++;
}

 

 

clear() 메서드

@Override
public void clear() {
    this.size = 0;
    this.head.next = null;
}

clear 메서드는 노드의 연결을 끊어주면 된다. 그래서 맨 처음 노드인 head의 다음 노드를 null로 바꿔 연결을 끊어줬다.

 

 

delete(E e) 메서드

delete는 중간 노드가 삭제 될 수 있으므로 insert 메서드와 같이 prev, curr 노드 두개가 필요하다.

그래서 curr 노드의 데이터가 매개변수와 같으면 prev의 다음 노드를 curr의 다음 노드로 연결하고, curr의 다음 노드를 null로 연결하여 끊어준다.

@Override
public boolean delete(E e) {
    Node prev = this.head;
    Node curr = prev.next;

    while (curr != null) {
        if (curr.data.equals(e)) {
            prev.next = curr.next;
            curr.next = null;
            size--;

            return true;
        }

        prev = prev.next;
        curr = curr.next;
    }

    return false;
}

 

 

deleteByIndex(int index) 메서드

@Override
public boolean deleteByIndex(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException();

    Node prev = this.head;
    Node curr = prev.next;

    int i = 0;
    while (i++ < index) {
        prev = prev.next;
        curr = curr.next;
    }

    prev.next = curr.next;
    curr.next = null;
    size--;

    return true;
}

delete 메서드와 개념은 같으므로 코드만 첨부해도 될 것 같다.

 

 

기타 메서드

나머지 get이나 indexOf 등 기타 메서드들은 노드 간의 연결을 재구성하는 게 필요없어서 추가, 삭제를 이해했다면 코드만 봐도 이해할 수 있을 것이다.

@Override
	public E get(int index) {
		Node curr = this.head;

		int i = 0;
		while (i++ < index) {
			curr = curr.next;
		}

		return curr.data;
	}

	@Override
	public int indexOf(E e) {
		Node curr = this.head;

		int i = 0;
		while (curr != null) {
			if (curr.data.equals(e)) {
				return i;
			}

			curr = curr.next;
			i++;
		}

		return -1;
	}

	@Override
	public boolean isEmpty() {
		return this.size == 0;
	}

	@Override
	public int size() {
		return size;
	}

구현을 해본 결과, 연결 리스트는 데이터 추가, 삭제 시 대상 노드가 맨 앞이라면 O(1)의 시간복잡도를 그게 아니라면 O(n)의 시간복잡도를 갖게된다. 그리고 검색 역시 순회를 해야하므로 O(n)의 시간복잡도를 갖게 된다.

---

시간복잡도

• 추가, 삭제 : O(1), O(n)
• 검색 : O(n)