[알고리즘] 연결 리스트

31 May 2021

java

연결 리스트 👩🏻‍🤝‍👩🏻👩🏻‍🤝‍👩🏻

연결 리스트란, 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 연결된 표현이다.

물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법이다.

연결 리스트는 노드로 구성되어 있는데, 데이터 필드와 링크 필드로 구성되어 있다.

데이터 필드에는 저장하고 싶은 데이터가 들어가고, 링크 필드에는 다른 노드를 가리키는 포인터가 저장된다.

😉 장점: 연속적인 기억공간이 없어도 데이터를 저장하는 것이 가능하며 미리 기억공간을 확보할 필요 ❌

😣 단점: 링크 필드를 위한 추가 공간이 필요하고, 순차탐색을 해야 하므로 탐색속도 떨어짐

따라서 ❗

탐색 혹은 정렬이 빈번히 일어나는 경우에는 배열을, 데이터의 추가 및 삭제 연산이 많을 경우에는 연결리스트를 사용하는 것이 좋다.

1. 단순 연결 리스트 (Simple Linked List)

단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용해 모든 노드들이 연결되어 있다.

마지막 노드의 링크 필드 값은 NULL이 된다.

아래는 단순 연결 리스트를 구현한 코드이다.

public class ListNode {
	Object data;
	ListNode link;
	
	public ListNode() {
		this.data = null;
        this.link = null;
	}
    
    public ListNode(Object data) {
        this.data = data;
        thius.link = null;
    }
    
    public Object getData() {
        return this.data;
    }
}

1-1. 단순 연결 리스트에서의 삽입

public LinkedList {
	private ListNode head;
    private int size = 0;
	
	public LinkedList() {
		this.head = null;
	}
    
    void insertFirst(Object input) {
        ListNode node = new ListNode(input);
        if (head == null) {
            head = node;
        }
        else {
            ListNode curr = head;
            node.link = curr;
            head = node;
        }
    }
    
    void insertNode(Object input, int k) {
        if (k == 0) {
            insertFirst(input);
        }
        else if (k == size) {
            insertLast(input);
        }
        else {
            // k 번째의 Node를 찾기 위한 Node(int idx) 메소드
        	ListNode tmp1 = Node(k-1);
            ListNode tmp2 = tmp1.link;
            ListNode newNode = new Node(input);
            
            tmp1.link = newNode;
            newNode.link = tmp2;
            size++;
        }
    }
    
    void insertLast(Object input) {
        ListNode node = new ListNode(input);
        if (size == 0) {
            insertFirst(input);
        }
        else {
            insert.link = node;
            size++;
        }
    }
}

1-2. 단순 연결 리스트에서의 삭제

void deleteNode(Object input) {
    ListNode node = new ListNode(input);
    
    if (head == null) {
		// 지울 노드 X
    }
    else {
        ListNode prev = head;
        ListNode curr = head.link;
        while (tmpNode.data != node.data) {
			prev = curr;
            curr = curr.link;
        }
        prev.link = curr.link;
    }
}

1-3. 단순 연결 리스트에서의 탐색

ListNode search(Object input) {
    ListNode node = new ListNode(input);
    if (head == null) {
        // 탐색할 노드 X
    }
    else {
        ListNode curr = head;
        while (curr.data != node.data) {
            curr = curr.link;
        }
        return curr;
    }
}

2. 원형 연결 리스트 (Curcular Linked List)

원형 연결 리스트란 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트이다.

단순 연결 리스트에서는 마지막 노드의 링크가 Null 이었지만, 여기서는 첫 번째 노드의 주소가 되는 것이다.

노드의 구현 자체는 단순 연결 리스트와 다르지 않다.

public class ListNode {
	Object data;
	ListNode link;
	
	public ListNode() {
		this.data = null;
        this.link = null;
	}
    
    public ListNode(Object data) {
        this.data = data;
        thius.link = null;
    }
    
    public Object getData() {
        return this.data;
    }
}

2-1. 원형 연결 리스트에서의 삽입

// 마지막 노드에 삽입하는 경우만 보도록 하자
public class Circular {
    private ListNode cl;
    
    void insertLast(Object input) {
        ListNode node = new ListNode(input);
        if (cl == null) {
            cl = node;
            node.link = node;
        }
        else {
            ListNode curr = cl;
            while (curr.link != cl) {
                curr = curr.link;
            }
            node.link = curr.link;
            curr.link = node;
        }
    } 
}

2-2. 원형 연결 리스트에서의 삭제

// 마지막 노드를 삭제하는 경우만 보도록 하자
void delete() {
    ListNode prev = cl;
    ListNode curr = cl.link;
    while (curr.link != cl) {
        prev = curr;
        curr = curr.link;
    }
    prev.link = curr.link;
}

3. 이중 연결 리스트 (Doubly Linked List)

단순 연결 리스트에서 어떤 노드에서 후속 노드를 찾기는 쉽지만, 선행 노드를 찾으려면 구조상 아주 어렵다.

이중 연결 리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다.

링크가 양방향이므로 양방향으로 검색이 가능해진다.

단점으로는 공간을 많이 차지하고 코드가 복잡해진다.

3-1. 이중 연결 리스트에서의 삽입

void addFirst(Object input) {
    Node node = new Node(input);
    if (head != null) {
        node.link = head;
        head.prev = node;
    }
    head = node;
    if (head.next == null) {
        tail = head;
    }
    size++;
}

3-2. 이중 연결 리스트에서의 삭제

Object removeFirst() {
    if (size == 0) {
        return null;
    }
    Node remove = head;
    head = null;
    head = remove.next;
    head.prev = null;
    size--;
    
    return remove.data;
}