선형리스트(개념)

선형리스트 (개념)

자료를 표현하는 방법: 1. 순차 자료구조 2. 연결 자료구조

리스트 중에 순서를 가지고 있는 것 - 선형리스트(순차리스트)

선형리스트 - 선형 순차 리스트(순차 리스트), 선형 연결 리스트(연결 리스트)

리스트는 보통 이렇게 표현한다:

  리스트 이름 = (원소1, 원소2, 원소3)
      ex) 게임 = (오버워치, 배틀그라운드, 위쳐3)

---

선형 리스트(선형 순차 리스트)

원소들 간의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같다. (순차 자료구조)

따라서 메모리에 연속적으로 순서대로 저장되기 때문에, 시작 위치/원소의 크기를 알면 특정 원소의 위치를 알 수 있다.

원소 삽입

1. 원래 있던 리스트에서 새 원소를 넣을 자리를 만들어준다. (원소들을 뒤로 밀어서 빈칸을 만들어줌)

2. 새 원소 삽입

원소 삭제

1. 원래 있던 리스트에서 특정 원소 삭제

2. 빈칸이 없도록 나머지를 앞으로 땡겨준다.

순차리스트의 장·단점

• 장점: 간단함 / 인덱스로 쉽게 엑세스 가능

• 단점: 원소 추가/삭제시 연속 저장의 순서를 유지해주어야 함 →오버헤드 발생.

  따라서, 삽입, 삭제 연산이 많을땐 비효율적!

---

배열의 순차 표현

메모리에 배열이 실제로 어떻게 저장되는가?

• 1차 배열

  1차 배열
  50	12	4	7

  메모리에는 50-12-4-7 순서대로 저장된다.

• 2차 배열

  • 
    

  2차 배열
  5	1	2	4
  85	24	13	34

  • 메모리에는 둘 중 하나의 방법으로 저장된다

    • 행 우선 방법: 5-1-2-4-85-24-13-34

    • 열 우선 방법: 5-85-1-24-2-13-4-34

  • 어떤 방법인지는 컴파일러에 따라 다르다. C컴파일러는 행 우선 방법을 사용한다.

• 3차 배열

  • 면 우선 방법: 차원 먼저

  • 열 우선 방법: 열 먼저

다항식의 순차 자료구조 표현

시간없어서 생략

행렬의 순차 자료구조 표현

시간없어서 생략