리스트

지난 글 : [알고리즘/Do it 알고리즘] - 보이어 • 무어법

 

리스트 살펴보기

참고 : [알고리즘/알고리즘 도감] - 리스트

리스트란 데이터를 순서대로 나열해 놓은 자료 구조를 말한다.

*이전에 배운 스택과 큐도 리스트 구조로 되어 있다.

 

선형 구조를 갖는 리스트에는 선형 리스트(linear list)와 연결 리스트(linked list)가 있다. 선형 리스트는 데이터가 배열처럼 연속(linear)하는 메모리 공간에 저장돼 순서를 갖는다. 연결 리스트는 데이터가 메모리 공간에 연속적으로 저장되어 있지 않더라도 각각의 데이터 안에 다음 데이터에 대한 정보를 갖고 있어 서로 연결(linked)된다. 이는 위 참고에 잘 나와 있다.

 

배열로 선형 리스트 만들기

비상 연락망을 선형 리스트로 저장하기 위해 간단한 배열로 구현해 아래에 나타냈다. 요소의 자료형인 Person인 배열 data의 요솟수는 3개다.

class Person {
	int No;
    String name;
    String phoneNo;
}

Person[] data = {
	new Person(12, "Jhon", "000-000-0001),
    new Person(33, "Paul", "000-000-0002),
    new Person(57, "Mike", "000-000-0003)
}

 

 

다음 노드 꺼내기

배열의 각 요소에는 연락할 순서대로 데이터가 저장돼 있다. 전화를 걸기 위해 필요한 '다음 노드 꺼내기'는 1만큼 큰 인덱스를 갖는 요소에 접근하면 된다.

 

노드의 삽입과 삭제

회원번호가 55인 회원이 새로 가입해 이 회원의 정보를 회원번호 12와 33 사이에 삽입하려 한다. 이때 삽입한 요소 이후의 모든 요소를 한 칸씩 뒤로 밀어야 한다. 삭제할 때도 삭제한 요소 이후의 모든 요소를 앞으로 당겨야 한다. 이런 별도의 작업이 필요하기에 배열로 구현한 선형 리스트는 아래와 같은 문제를 갖는다.

- 쌓이는 데이터의 최대 크기를 미리 알아야 한다.
- 데이터를 삽입, 삭제할 때마다 많은 데이터를 옮겨야 하므로 비효율적이다.

 

 

참고 서적 :