[Algorithm] 리스트

오늘은 자료구조의 리스트에 대해서 알아보도록 하자

List

List 는 순서를 가진 데이터의 집합을 가진 추상자료형이다. 중복이 상관없다. 배열 기반의 순차 리스트와 메모리 주소 연결을 통한 연결 리스트가 존재한다.

순차 리스트

먼저 배열 기반의 순차 리스트에 대해서 알아보자. 모든 데이터들이 1차원 배열에 순서대로 저장된 형태를 말한다. 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 구현할 수 있다. 또한 모두 알다시피 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다.

삽입 시에는 삽입하는 항목 이후의 항목들을 모두 이동해야한다. 이때 인덱스가 높은 것부터 먼저 이동시켜야 데이터가 겹치지 않고 모두 이동할 수 있다.

삭제 시에도 동일하게 삭제하는 항목 이후의 모든 항목을 왼쪽으로 이동시켜야한다. 하지만 이때는 방향이 반대이므로 인덱스가 낮은 것부터 옮겨야한다.

• 단순 배열 사용해 순차 리스트를 만들면 삽입, 삭제 시 원소들을 이동하는 작업이 필요하다. 따라서 원소의 개수가 많고 삽입,삭제가 빈번하면 비효율적이다. 배열의 크기가 정해져있는 경우 원소가 배열의 크기보다 적으면 쓰이지 않는 배열의 메모리가 낭비되는 것이고, 원소가 배열의 크기보다 커지면 재할당해야하므로 메모리 소요가 필요하다.

연결 리스트

연결 리스트를 사용하면 순차 리스트의 문제를 해결할 수 있다. 연결 리스트는 논리적인 순서나 메모리 물리적인 순서가 일치하지 않고 개별적으로 위치한 주소를 연결하여 하나의 자료구조를 이룬다. 링크를 통해 연결되기 때문에 물리적인 순서를 맞추기 위한 작업이 필요없다. 순차 리스트와 다르게 크기를 동적으로 조정해서 효율적이다. 하지만 구현이 복잡하다는 단점이 존재한다. 연결 리스트에는 노드와 헤드가 존재한다. 노드는 하나의 원소에 필요한 실질적 데이터를 가지고 있으며 데이터 필드와 링크 필드로 나뉜다. 헤드는 연결 리스트의 처음 노드를 가르키는 구조로 데이터는 가지고 있지 않다.

리스트는 연결하는 방식에 따라 다시 몇 가지로 나눌 수 있다.

단순 연결 리스트

노드가 하나의 링크 필드에 의해 다음 노드와 연결되어있는 형태이다. 리스트는 헤드부터 쭉 연결되어있고 마지막 노드의 링크 필드는 null 이다.

삽입 할 때 새로운 노드를 생성하고 데이터를 저장한다. 삽입될 위치의 바로 앞 노드의 링크 필드(그 다음 노드의 주소)를 자신의 링크 필드로 가져오고 자신의 주소를 앞 노드의 링크 필드에 저장한다. 삭제 시 앞 노드가 다음 노드를 가르키게 만든다. 이때 메모리 누수에 주의해야하며 꼭 삭제한 노드의 메모리를 해제해주어야한다.

이중 연결 리스트

단순 연결 시에는 앞으로 이동할 수 없어 앞의 노드로 이동하기 위해서는 다시 헤드부터 접근해야한다는 단점이 있다. 따라서 앞뒤로 모두 이동할 수 있도록 링크 필드를 앞 뒤 2개로 만든 것이 이중 연결 리스트이다.

삽입 시 새로운 노드를 생성하고 앞뒤 주소값을 복사한 후 앞뒤 노드의 링크 필드를 자신의 주소로 연결한다. 삭제 연산 시에는 서로 건너편 주소를 연결한다.

리스트의 활용

해당 리스트를 실제 자료구조로 활용할 때 사용할 수 있고 대표적으로 stack, 우선순위 Queue 를 구현할 수 있다.

stack

• 순서는 링크를 통해 연결
• push : 마지막 노드 삽입
• pop : 마지막 노드 반환, 삭제
• top :: 마지막 노드를 가르킨다.

우선순위 Queue

• 원소를 삽입할 때 우선순위를 비교해 적절한 위치에 삽입한다. 가장 앞에 최고 우선순위의 원소가 위치한다. 배열로 구현하면 삽입 시 원소의 재배치가 계속해서 이루어져야하기 때문에 메모리가 비효율적으로 사용된다. 따라서 연결 리스트를 활용하는 것이 효율적이다!

---

LinkedList<Integer> list = new LinkedList<>();

Java 에서 위의 LinkedList 를 사용하면 쉽게 연결 리스트를 정의할 수 있다. add, remove, get 등 편리한 함수들도 역시 가지고 있으니 삽입, 삭제가 빈번한 배열에서는 LikedList 를 사용하도록 하자!