[C언어 #58] 연결 리스트 (Linked lists) - item을 arraylist에 추가

c언어 연결 리스트 (Linked lists)

 

• array lists 문제점

  list 중간에 삽입이나 삭제가 어렵다

  - 이를 수행하기 위해서는 공간 확보를 위해서 많은 아이템들이 이동을 해야 한다

 

• ex. 중간에 소수 삽입

      소수 primes → [ 2,  ] →  [ 3,  ] →  [ 7,  ] →  [ 11,  ]
      소수 5 삽입 (insertion)
      소수 primes → [ 2,  ] →  [ 3,  ] -----------→  [ 7,  ] →  [ 11,  ]
      소수 primes → [ 2,  ] →  [ 3,  ] →  [ 5,  ] →  [ 7,  ] →  [ 11,  ]

 

• 소수 5를 리스트에 삽입하기 위한 절차

      1. 3과 7을 가지고 있는 구조체 (structures)를 찾는다.

      2. 새로운 구조체를 위한 공간 할당(allocate)

      3. 첫번째 필드를 5로 지정

      4. 두번째 필드가 7 구조체를 가리키도록 설정

      5. 3구조체의 포인터가 새로운 구조체를 가리키도록 설정

 

• 리스트 항목들이 메모리에 흩어지게 되겠지만, 각 항목이 다음 항목을 가리키도록 지정해 놓았기에 찾을 수 있다.