LinkedList

class MyLinkedList<E> {
    private class Node<E>(var item: E, var next: Node<E>?, var prev: Node<E>?)

    private var size = 0
    private var first: Node<E>? = null
    private var last: Node<E>? = null

    fun add(e: E) {
        val l = last
        val newNode = Node(e, null, l)
        last = newNode

        if (l == null)
            first = newNode
        else 
            l.next = newNode

        size++
    }

    fun remove(index: Int): E? {
        checkElementIndex(index)

        return unlink(node(index))
    }

   // Get the node at a specific index.
   private fun node(index: Int): Node<E> {
       if (index < (size shr 1)) {
           var x = first
           for (i in 0 until index)
               x = x?.next
           return x!!
       } else {
           var x = last
           for (i in size - 1 downTo index + 1)
               x= x?.prev
           return x!!
       }
   }

   // Unlink the non-null node from the list.
   private fun unlink(x: Node<E>): E? {
       val elementData = x.item 
       val nextNodeData= x.next 
       val prevNodeData= x.prev 

       if(prevNodeData == null){
          first= nextNodeData  
       }else{
          prevNodeData.next= nextNodeData  
          x.prev=null  
      }
      
      if(nextNodeData==null){
         last=prevNodeData  
      }else{
         nextNodeData.prev=prevNodeData  
         x.next=null   
     }
     
     size--
     return elementData 
   }

   // Check if the given index is in range. If not, throw an appropriate runtime exception.
   private fun checkElementIndex(index: Int) {
       if (!isPositionIndex(index))
           throw IndexOutOfBoundsException()
   }
   
   // Tells if argument is the index of a valid position for an iterator or an add operation.
   private fun isPositionIndex(index:Int):Boolean{
     return index in 0..size 
}
}

• add 함수: 새로운 요소를 리스트의 마지막에 추가한다다. 새로운 노드(newNode)를 생성하고 이전 노드(prev)로 마지막 노드(last)를 지정한다. 그런 다음 last 포인터를 새로운 노드로 업데이트한다. 만약 리스트가 비어있다면 (l == null), 첫 번째 노드(first)도 새로운 노드로 설정한다. 그렇지 않다면 이전 마지막 노드의 next 포인터를 새로운 노드에 연결한다. 마지막으로 리스트의 크기(size)를 하나 증가시킨다.

• remove 함수: 주어진 인덱스에 위치한 요소를 제거한다. 유효성 검사 후 해당 인덱스 위치에 있는 실제 노드 객체(node(index))을 가져온다. 그 후 unlink(x) 메서드에서 실제 삭제 로직이 수행된다.

• node 함수: 특정 인덱스에 있는 노드를 반환합니다. 만약 찾는 인덱스가 리스트 크기의 절반보다 작다면 처음부터 찾는다. 그렇지 않으면 마지막부터 찾아간다.

• unlink 함수: 링크가 해제된(즉, 제거되는) 노드 x에서 원소를 반환하고, 해당 원소 앞뒤의 링크들을 재연결한다.

• checkElementIndex 및 isPositionIndex 함수: 주어진 인덱스가 유효한 범위 내에 있는지 확인하고, 아니라면 예외를 발생시킨다.

ArrayList

class MyArrayList<E> {
    var elementData: Array<Any?> = arrayOfNulls(10)
    var size: Int = 0

    fun add(e: E) {
        ensureCapacityInternal(size + 1)  // Check if the current array can accommodate the new element
        elementData[size++] = e // Add the new element at the end of array and increment the size
    }

    fun remove(index: Int): E {
        rangeCheck(index) // Check if index is valid 

        val oldValue = elementData[index] as E // Store old value in a variable

        val numMoved = size - index - 1 
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved) // Shift any subsequent elements to fill up the space created by removal
                             
        elementData[--size] = null // Decrement size and set last value to null

        return oldValue 
    }
    
    private fun ensureCapacityInternal(minCapacity: Int) {
         if (minCapacity - elementData.size > 0)
             grow(minCapacity)
     }
     
     private fun grow(minCapacity: Int){
         val oldCapacity=elementData.size
         var newCapacity=oldCapacity+(oldCapacity shr 1)

         if(newCapacity-minCapacity<0){
             newCapacity=minCapacity
         }

         elementData=newElementArray(new_capacity)
     }
     
     private fun rangeCheck(index: Int) {
         if (index >= size || index < 0 )
             throw IndexOutOfBoundsException()
     }
}

• add 함수: 이 함수는 새로운 요소를 ArrayList에 추가한다. 먼저 ensureCapcityInternal(size + 1)을 호출하여 충분한 용량이 있는지 확인한다. 만약 현재 배열의 용량이 부족하다면 배열 크기를 확장하는 로직(grow)이 실행된다. 그 다음으로 elementdata[size++] = e에서 실제 요소를 추가하고, 리스트의 크기(size)를 증가시킨다.

• remove 함수: 이 함수는 주어진 인덱스에 위치한 요소를 제거한다. 먼저 rangeCheck(index)를 호출하여 인덱스가 유효한지 확인한다. 유효하지 않은 경우 IndexOutOfBoundsException 예외가 발생한다. 그 후 제거할 값을 임시 변수에 저장하고 (val oldValue = elemenTdata[index]) , 제거된 요소 뒤에 있는 모든 요소들을 앞으로 한 칸씩 이동시킨다.
  (System.arraycopy(elementData, index+1, elementData, index,numMoved)).
  마지막으로 리스트 크기(size)를 줄이고 (--size) 마지막 원소 자리(null로 설정함으로써 가비지 컬렉션 대상으로 만든다), 제거된 값을 반환한다.

• ensureCapacityInternal 함수: 이 함수는 현재 ArrayList의 용량이 새 요소를 추가하기에 충분한지 확인한다. 만약 용량이 부족하다면 grow 함수를 호출하여 배열의 크기를 늘린다.

• grow 함수: 이 함수는 ArrayList의 용량을 늘리는 역할을 한다. 기존 용량의 절반만큼 더 늘리되, 그 결과가 필요 최소 용량보다 작으면 필요 최소 용량으로 설정한다.

• rangeCheck 함수: 이 함수는 인덱스가 유효한 범위 내에 있는지 확인한다. 인덱스가 범위를 벗어나면 IndexOutOfBoundsException 예외를 발생시킨다.