리스트(List)

리스트(List)

순서를 가진 데이터의 집합을 가리키는 추상자료형(abstract data type)

동일한 데이터를 가지고 있어도 상관 없다. 데이터 중복 허용

순서 -> index 관리(offset)

구현 방법에 따라 크게 두 가지로 나뉜다.

1. 순차 리스트 : 배열을 기반으로 구현된 리스트
2. 연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트

순차 리스트

구현 방법

1차원 배열에 항목들을 순서대로 저장

데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있다.

데이터 접근 : 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다.

삽입 연산 : 삽입 위치 다음의 항목들을 뒤로 이동해야 한다.

삭제 연산 : 삭제 위치 다음의 항목들을 앞으로 이동해야 한다.

순차 리스트의 문제점

단순 배열을 이용한 순차리스트를 구현해 사용하는 경우, 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요하다.

원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가한다.

배열의 크기가 정해져 있는 경우, 실제로 사용될 메모리보다 크게 할당하여 메모리의 낭비를 초래할 수도 있고, 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어 작업을 해야하는 경우가 발생할 수도 있다.

고정된 길이로 사용하는 것이 제일 바람직하다.

연결 리스트(Linked List)

특성

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 각 원소를 연결하여 하나의 전체적인 자료구조를 이룬다.

독립적인 객체(동적할당)

링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.

자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.

연결 리스트의 기본 구조

노드(Node)

연결 리스트에서 하나의 원소(data)를 표현하는 building block

구성요소

1. 데이터(data)s 필드

   • 원소의 값을 저장
   • 저장할 원소의 종료나 크기에 따라 구조를 정의하여 사용함

2. 링크(link) 필드

   • 다음 노느듸 참조값을 저장

헤드

연결 리스트의 첫 노드에 대한 참조값을 갖고 있음

dummy node : 관리의 용이성을 위해서, 다음 노드부터 데이터 노드

head : 첫 번째 노드의 참조값, 헤드 == 첫 노드

연결 리스트의 종류

단순 연결 리스트 : 링크 하나

삭제시 삭제할 노드의 이전 노드를 알아야 한다.

이중 연결 리스트 : 링크 두 개, 양방향으로 관리

이중 연결을 통해 이전 노드를 관리, 삭제 시 이전의 링크를 확인

원형 연결 리스트 : 단순 원형 연결 리스트, 이중 원형 연결 리스트

어떤 기준 노드로 시작해도 전체 리스트 탐색 가능

목적에 따라 다른 사용

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

노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가진다.

헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리키니다.

링크 필드가 Null 인 노드가 연결 리스트의 가장 마지막 노드이다.

첫 번째 노드로 삽입

addtoFirst(L, i)        // 리스트 헤드 L, 원소 i

   new <- creatNode()   // 새로운 노드 생성
   new.data = i         // 데이터 필드 작성
   new.link = L         // 링크 필드 작성
   L = new              // 리스트의 처음으로 지정

end addtoFirst() 

마지막 노드로 삽입

addtoLast(L, i)               // 리스트 헤드 L, 원소 i

   new <- createNode()        // 새로운 노드 생성
   new.data = i
   new.link = Null

   if (L == Null)             // 빈 리스트일 때, 최초 노드 추가
      L = new
      return

   temp = L                   // 노드 링크 이용하여 리스트 순회
   while(temp.link != Null)   // 마지막 노드 찾을 때까지 이동
      temp = temp.link

   temp.link = new            // 마지막 노드 추가

end addtoLast()

가운데 노드로 삽입

노드 pre 다음 위치에 노드 삽입

add(L, pre, i)                // 리스트 헤드 L, 노드 pre, 원소 i

   new <- createNode()        // 새로운 노드 생성
   new.data = i               // 데이터 필드 작성

   if (L == Null)             
      L = new
      new.link = Null

   else
      new.link = pre.link
      pre.link = new

end addtoLast()

삭제 연산

target 노드 삭제

delete(L. target)                             // 리스트 헤드 L, 삭제노드 target

   if(L == Null || target == Null) return

   pre = getPreNode(target)                  // 선행노드 탐색

   if (pre == Null)
      L = target.link

   else
      pre.link = target.link

   terget.link = null

end delete()

논리적 순서를 유지하기만 하면 된다.

차례대록 계속 덧붙이는 형태 삽입, 차례대로 지워나감

삽입과 삭제가 한 방향으로, 첫 노드로 삽입, 삭제

스택으로 구현

push로 첫 노드 삽입

pop으로 첫 노드 삭제

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

양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

두 개의 링크 필드와 한 개의 데이터 필드로 구성