[APS] 006 : 자료구조 - 연결리스트

연결리스트

---

 

노드(Node)

class Node<E> { //Java 에서는 클래스(객체)로 표현
    E data;
    Node<E> link;
    
    Node(E data) {
        this.data = data;
        this.next = null;
    }
}

 

- 연결리스트나 트리와 같은 자료구조에서 원소를 표현하는 최소단위

- 데이터 필드 / 링크 필드 두개의 내부 데이터를 지님

• 데이터 필드(data field) : 원소가 갖는 고유의 값을 저장하는 변수
• 링크 필드(link field) : 다른 노드에 대한 참조값(= 메모리주소) 을 저장하는 변수

※ 노드는 본래 네트워크 등에서 데이터를 전송하는 연결지점, 즉 '단말'을 의미하는 단어이다.

---

연결리스트(Linked-List)

 - 원소(node)간의 연결을 통해 데이터를 순서대로 저장하는선형 자료구조 

• index를 이용해 데이터에 접근할 수 있으나 배열에 비해 느림
• 자료의 논리적 구조와 물리적 구조가 일치하지 않아 배열에 비해 캐시 메모리 적중률 이 낮음
• 자료의 삽입과 삭제가 배열에 비해 빠름

- 헤드(Head) 노드 : 연결리스트의 첫 노드

- 테일(Tail) 노드 : 연결리스트의 마지막 노드 

※ 헤드를 따로 노드로 구현하지 않고, 연결리스트 객체의 고유값으로 나타내기도 한다.

---

연결리스트의 종류

1. 단순(singly) 연결리스트 : 다음 순서의 노드와 연결되며 테일 노드에는 null값이 저장된 연결리스트
2. 원형(circular) 연결리스트 : 테일 노드의 링크 필드가 헤드 노드와 연결되도록 구현된 연결리스트
3. 이중(double) 연결리스트 : 이전 순서의 노드, 다음 순서의 노드 모두 링크필드에 저장된 리스트

---

연결리스트과 복잡도

1.시간 복잡도

- 접근 / 변경 : O(N)

• 원하는 인덱스의 노드까지 순차적으로 순회해야 하므로 O(N)이 소요

- 삽입 / 삭제 : O(1) 

• 삽입과 삭제 모두 노드의 링크 필드 내의 데이터만 덮어쓰면 되므로 O(1)

※ 연결리스트는 index값으로 바로 데이터에 접근하는 랜덤 액세스(Random Access)가 불가능하다. 따라서 특정 index의 값을 삽입/삭제하기 위해선 해당 노드까지 순회하는 최대 O(N)만큼의 시간이 더 필요하다. 이중 연결리스트는 탐색시 테일 노드부터 순회할 수 있으므로 평균적으로 단순/원형 연결리스트보다 효율적인 탐색이 가능하다. 

 

2. 공간 복잡도

 - O(N) 연결리스트의 각 노드는 링크 필드에 주소값을 저장하므로, 추가적인 메모리(overhead)가 소요됨

• 주소값의 용량은 CPU의 비트에 비례(32bit CPU : 4byte / 64bit CPU : 8byte)

 - 따라서 배열/동적배열보다 연결리스트의 실제 메모리 사용량이 훨씬 큼

---

---

Java 연결리스트

---

LinkedList

- Java 는 List 인터페이스를 상속받는 LinkedList 클래스가 연결리스트를 구현하고 있음

List<Integer> list = new LinkedList<>();
// 이중 링크드리스트 선언

Collections.sort(list); //리스트 정렬

- 이전 / 이후 참조 값을 갖는 노드를 사용하는 이중 연결리스트로 구현

- Queue 등의 많은 자료구조가 LinkedList를 상속하여 구현

---

- 최종 수정일 : 23-04-10

- 이 글은 지속적으로 수정되고 있으며, 오타나 잘못된 정보에 대한 사항은 댓글로 남겨주시면 감사하겠습니다.