[자바/자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List)

 연결 리스트는 노드(Node)라는 단위로 데이터를 저장하는 자료구조다. 배열처럼 일정한 크기의 메모리 공간을 할당받아 데이터를 저장하는 것이 아닌 노드(데이터)가 삽입될 때마다 메모리를 할당받고 마지막 노드가 새로운 노드에 대한 참조를 저장해 나가는 방식으로 리스트를 구성한다.

 

 

 노드(Node)

 연결 리스트는 데이터를 저장할 때 노드(Node) 단위로 데이터를 저장하는데 노드는 데이터와 또 다른 노드가 있는 곳을 가리키는 참조 변수로 구성된다. 여기서 참조 변수는 리스트의 구현 방식에 따라 1개가 될 수도 있고 2개 이상이 될 수도 있다. 

 

Node Class of Singly Linked List

 Node를 클래스로 표현하면 위와 같다. 이 노드는 단일 연결 리스트의 노드 클래스로 연결 리스트 중에서는 가장 최소화된 구조라고 할 수 있다.(element가 데이터, next가 link) 노드 클래스는 연결 리스트의 종류에 따라 링크의 개수, 변수 이름(역할에 따른 직관성)정도가 달라질 뿐 같은 형태를 취하고 있다.

 

 

 

배열과 연결 리스트

배열, 연결 리스트가 할당된 메모리 상태

 

 Array

 배열은 초기화할 때 할당받은 크기로 메모리 길이가 고정되며, 할당받은 공간만큼의 메모리만 사용할 수 있다는 특징이 있다. 이러한 특징은 저장할 데이터의 개수가 정해져 있을 때에는 메모리 공간 낭비가 없어 효율적이지만 저장할 데이터의 개수를 모르는 상황에서는 다르다. 배열의 특성상 메모리 공간을 할당받으려면 크기가 명확하게 정해져야 하기 때문에 저장될 데이터 수를 정확히 모르더라도 예상해서 공간을 할당받을 수밖에 없다. 이 과정에서 너무 많은 공간을 할당받는 것은 메모리 누수를 초래할 수 있고 반대로 너무 적은 공간을 할당받으면 오버 플로우를 초래하게 된다.

 

 

 Array, LinkedList

 반면 연결 리스트는 배열에 비해 공간 확장의 제한을 받지 않는다. 왜냐하면 배열처럼 메모리 공간을 미리 할당받지 않고 데이터가 삽입될 때마다 메모리를 할당받은 뒤 노드끼리는 참조로 연결되기 때문이다. 이러한 구조는 고정적인 크기의 배열과 달리 메모리 공간이 허용하는 한 계속해서 노드를 늘려갈 수 있다.

 

 

 

연결 리스트 노드 삽입

 연결 리스트를 조작하는 방법 중 삽입에 대해서만 알아보자. 

단일 연결 리스트 데이터 삽입 과정

 연결 리스트 객체는 Node 타입의 head라는 멤버 변수를 갖는다. head는 null로 초기화되어 있다가 처음으로 노드가 추가될 때 비로소 초기화되며 이 때 link는 null 값을 가진다. link는 다른 노드의 참조값이나 null 중 하나가 초기화되는데 참조값을 가진 경우 연결된 노드가 있다고 보고 null일 경우 해당 노드가 마지막이라고 본다. 따라서 첫 노드가 head에 초기화되었고 link에 null을 초기화하고 있다는 것은 이 노드가 처음이자 마지막이라는 뜻이 된다.

 

 두 번째 노드부터는 연결 리스트의 끝, 즉 마지막 노드의 뒤에 노드를 추가한다. 마지막 노드를 찾기 위해선 연결 리스트의 head 노드가 가진 링크를 시작으로 노드를 계속해서 참조해나가나다 link가 null인 노드를 찾으면 순회를 멈추고 다시 노드를 연결한다.

 

 

 

연결 리스트 종류

  연결 리스트는 크게 3가지 종류가 있다. 

• 단일 연결 리스트(Singly Linked List)
• 이중 연결 리스트(Doubly Linked List)
• 원형 연결 리스트(Circular Linked List)

 이 외에 청크 연결 리스트(Chunked Linked List), 다중 연결 리스트(Multi Linked List) 등이 있다.

 

 

단일 연결 리스트(Singly Linked List)

Singly Linked List

 단순 연결 리스트라고도 하며 연결 리스트들 중에서 가장 기본이 되는 연결 리스트로, 각 노드는 다음 노드에 대한 정보만을 가지고 노드끼리는 서로 인식하지 못하는 기본적인 구조를 띄고 있다. 구현 난이도는 ArrayList보다 약간 어려운 정도다. 

 

 

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

Doubly Linked List

 양방향 연결 리스트라고도 하며 단일 연결 리스트와 다르게 이전 노드의 링크를 저장하고 있다는 것이 특징이다. 노드는 자신의 앞뒤 노드를 인식하고 있기 때문에 노드를 순회하다가 앞으로 돌아갈 일이 생기면 링크를 따라서 이전 노드로 돌아갈 수 있다. 노드를 연결/삭제할 때마다 이전 노드까지 신경 써줘야 하지만 단일 연결 리스트를 구현할 수 있다면 이 또한 어렵지 않게 구현할 수 있다.

 

 

 원형 연결 리스트(Circular Linked List)

Circular Linked List

 환형 연결 리스트라고도 하며 특징은 그럼처럼 리스트의 마지막 노드가 null이 아닌 첫 번째 노드를 가리키고 있다는 점이다. 앞서 나온 두 리스트와는 달리 노드의 끝에 도달해도 끝나지 않고 head로 돌아가는 것이 특징이다.

 

 

 

연결 리스트의 head, tail

 연결 리스트의 끝을 가리키는 tail

 연결 리스트의 처음 위치에 데이터를 삽입한다고 생각해보자. 첫 번째 노드 즉, head의 앞에 삽입하면 되는 매우 간단한 작업이다. 새로운 노드의 다음 링크를 head로 지정한 뒤 연결 리스트가 가리키는 head의 위치를 새로운 노드로 변경해 주면 된다.

 

 반대로 연결 리스트의 끝에 노드를 삽입한다고 생각해보자. 데이터를 삽입하려면 마지막 노드를 알아야만 한다. 새로 생성한 노드를 마지막 노드로 만들기 위해서는 현재 마지막 노드의 link를 수정해야 하기 때문이다. 마지막 노드를 찾는 것은 매우 간단하다. 그냥 head부터 연결된 모든 노드를 거치면 된다. 구현도, 이론도 매우 간단하지만 데이터가 많을 수록 거쳐야 하는 노드가 늘어나는 문제가 있다. 

 

 여기서 tail이 등장한다. 말 그대로 꼬리, 연결 리스트가 헤드와 더불어 마지막 노드의 참조를 가지는 것이다. 첫 번째 노드(head)와 더불어 마지막 노드(tail)에 대한 참조를 가지고 있으면 리스트 양 끝에 한 번에 접근이 가능하다.

 

 tail을 무조건 구현해야 하는 것은 아니다. 상황에 따라 head만 필요한 경우도 있기 때문에 상황에 맞게 구현하면 된다.