[TIL 24.07.10] 08.선형 자료구조 - LinkedList

.

 

목   차

 

확인 문제

1. LinkedList가 무엇인지 알고 있나요? 어떤 방식으로 작동하는지 설명할 수 있을까요?

LinkedList는 각 데이터 요소들을 노드로 구성하고 각 노드는 다음 노드를 가리키는 포인터를 가지는 자료구조이다. 각 노드는 메모리 상에서 연속적인 위치가 아닌 곳에 존재할 수 있다. 

노드는 최소 2개의 필드를 갖는다. 

1. 노드 자체가 담고 있을 데이터. 

2. 다음 노드의 주소를 가리키는 포인터.

 

이때, 포인터의 값이 null이라면 기본적으로 노드의 끝이라는 의미를 갖는다. 

 

새로운 노드를 추가하려면 우선 새 노드 객체를 만든다.

만약 이 노드가 최초의 노드라면, 포인터는 반드시 null일 것이다. 

 

이 노드가 두 번째 노드라면, 2가지 선택지가 있다. 기존 노드의 앞에 배치되느냐, 뒤에 배치되느냐. 

앞에 배치된다면 이 노드의 포인터 주소를 기존 노드로 설정하면 된다. 뒤에 배치된다면 첫 번째 노드의 포인터 값을 새로운 노드로 설정하면 된다. 

 

세 번째 노드부터는 새로운 선택지가 생긴다. 가운데에 노드를 끼워넣기.

이때 끼워넣을 위치의 앞쪽 노드의 포인터 값은 새로운 노드를 가리키도록 수정하고, 새로운 노드의 포인터 값은 뒤쪽 노드를 가리키도록 하면 원하는 위치에 새로운 노드를 삽입하는 작업이 끝난다.

 

링크드 리스트의 경우, 반드시 첫 번째 노드부터 탐색을 할 수 있도록 되어 있다. 탐색은 첫 번째 노드에서 시작하여 각 노드의 포인터를 따라가면서 순차적으로 진행된다. 이는 특정 노드를 찾기 위해 모든 노드를 하나씩 확인해야 한다는 의미로, 최악의 경우 O(n) 시간이 소요된다.

또한, 링크드 리스트에서 노드를 삭제할 때는 삭제할 노드의 이전 노드를 찾아 포인터를 수정해야 한다. 이는 다음 노드를 가리키는 포인터를 삭제할 노드의 다음 노드로 변경함으로써 이루어진다. 이러한 구조 때문에 링크드 리스트는 임의 접근이 불가능하며, 특정 위치의 노드를 찾기 위해서는 순차 탐색이 필요하다.

2. LinkedList를 직접 구현해본 경험이 있을까요? 없다면 직접 구현해봅시다.

C++을 통해 직접 구현해본 경험이 있다. Node는 Struct로, LinkedList는 Class의 형태로 만들었으며 포인터로 각 노드는 내 앞과 뒤의 주소들을 알고 있도록 더블 링크드 리스트로 만들었다. 행렬을 표현하기 위해 각 노드가 자기 자신의 위쪽 아래쪽 원소 역시 가리키도록 한 경험도 있다.

 

---

 

설명 문제

1. LinkedList의 특성을 설명해주세요.

• 동적 크기 조정: 배열과 달리 미리 크기를 지정할 필요가 없으며, 필요에 따라 크기를 동적으로 조정할 수 있다.
• 노드의 연결: 각 노드는 데이터를 저장하고, 다음 노드에 대한 참조(포인터)를 가지고 있다.
• 메모리 할당: 노드들이 메모리의 비연속적인 부분에 저장될 수 있어, 연속적인 메모리 할당이 필요하지 않다.
• 삽입/삭제 효율성: 특정 위치에서 요소를 삽입하거나 삭제하는 것이 빠르다.
• 순차 접근: 임의 접근이 불가능하며, 첫 노드부터 순차적으로 접근해야 한다.

 

2. LinkedList는 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?

삽입 삭제가 빈번하고, 그 위치가 항상 맨 앞이거나 뒤가 아닐 때, 중간위치일 때 특히 사용하기 좋다. 

동적 메모리 할당이 필요할 때 역시 LinkedList가 유용하다.

 

임의접근이 필요하다면, LinkedList의 사용은 불편을 초래한다. 반드시 첫 노드부터 순서대로 접근해야 하는 특성 때문이다. 

메모리 오버헤드가 발생하기 쉽다. 포인터의 추가 저장 때문이다.

간단한 자료구조에 역시 부적합할 수 있다. 그 경우 배열 등을 사용하는 것이 효율적다.

3. LinkedList를 본인의 프로젝트에 적용해본 경험을 말해주세요.

LinkedList를 활용하여 지하철 노선도를 구현한 경험이 있다. 이 프로젝트에서는 출발역과 도착역, 그리고 그 사이의 노선 정보를 저장하고 최단경로를 찾는 시스템을 개발했다. 이를 위해 각 역을 노드로 표현하고, 각 노드는 다음 역을 가리키는 포인터를 가지는 링크드 리스트 구조를 사용했다.

 

먼저, dstNode 구조체는 각 도착역의 정보를 저장하는 노드로, 노선 타입(lineType), 도착역 이름(dstStationName), 다음 도착역을 가리키는 포인터(nextDst)를 포함한다. 노드의 생성자에서는 기본 값을 설정하고, 소멸자에서는 다음 도착역 노드를 재귀적으로 삭제하여 메모리 누수를 방지했다.

struct dstNode { 
	int lineType; //src&dst 사이 노선 종류. (1이상 9이하 자연수.)
	string dstStationName; //도착역 이름. (영어, 30자 이하.)
	dstNode* nextDst; //src에 대한 다음 dst를 가르키는 포인터.

	/*노드 생성자.*/
	dstNode(int line = 0, string data = "", dstNode* next = 0)
		:lineType(line), dstStationName(data), nextDst(next) { }
	~dstNode() { delete nextDst; }
};

 

이러한 dstNode를 연결하여 출발역을 관리하는 클래스가 srcChain이다. srcChain 클래스는 출발역 이름(srcStationName)과 첫 번째 도착역 노드를 가리키는 포인터(firstDstNode)를 멤버로 가진다. 이 클래스는 도착역 노드를 삽입하기 위한 Insert 메서드와 재귀적으로 도착역 노드를 삽입하는 헬퍼 함수 dstInsert, 그리고 체인을 초기화하는 chainRefresh 메서드를 포함한다.

class srcChain {
	friend class Graph; //Graph의 private멤버 접근허용.

	string srcStationName; //출발역 이름. (영어, 30자 이하.)
	dstNode* firstDstNode; //chain의 첫 노드를 가르키는 포인터.

	/*체인 생성자*/
	srcChain(dstNode* startNode = 0) 
		:srcStationName(""), firstDstNode(startNode) { }
	~srcChain() { delete firstDstNode; }
	/*첫 노드포인터 추가해서 dstInsert로 토스*/
	void Insert(int line, string data) { dstInsert(firstDstNode, line, data); }
	/*Insert 헬퍼함수*/
	void dstInsert(dstNode*& ptr, int& line, string& data) {
		if (ptr == 0)
			ptr = new dstNode(line, data);
		else
			dstInsert(ptr->nextDst, line, data); //재귀함수.
	}
	void chainRefresh() {
		if (firstDstNode != 0) {
			dstNode* temp = firstDstNode;
			firstDstNode = 0;
			delete temp;
		}
	}
};

 

이 구조를 기반으로 지하철 노선도를 나타내는 클래스가 Graph이다. Graph 클래스는 전체 역의 수(stations), 노선의 수(lines), 현재까지 등록된 역의 수(lastChainNum), 그리고 출발역 체인의 동적 배열(adjList)을 멤버로 가진다. 그래프 생성자에서는 동적 배열을 초기화하고, 소멸자에서는 할당된 메모리를 해제한다. Graph 클래스는 edgeInput 메서드를 통해 노선 정보를 입력받아 그래프를 구성하며, ShortestPath 메서드를 통해 최단 경로를 찾고 출력한다. 또한, findStationCode, IsInsertedEdge, timePrint 등의 헬퍼 메서드를 포함하여 역 이름에 맞는 코드를 찾고, 이미 입력된 노선인지 판별하며, 걸린 시간을 출력한다.

class Graph {
	int stations; // = num of vertices
	int lines; // = num of edges
	int lastChainNum; //현재까지 등록된 역의 수.
	srcChain* adjList; //src 체인의 동적 배열.

public:
	/*그래프 생성자*/
	Graph(const int vertices = 0)
		:stations(vertices), lines(0), lastChainNum(0) { adjList = new srcChain[vertices]; }
	/*그래프 소멸자*/
	~Graph() { delete[] adjList; }
	/*fin 입력*/
	void edgeInput(int line1, string src, int line2, string dst);
	/*최단경로 찾고 출력, 걸린 시간 출력, 중점역 출력*/
	void ShortestPath(string src, string dst);
private:
	/*역 이름에 맞는 코드 찾기(코드 = srcChain 동적배열의 src 위치.)*/
	int findStationCode(string data);
	/*이미 입력된 edge인지 판별*/
	bool IsInsertedEdge(int srcCode, int line, string dst);
	/*걸린 시간 출력하는 함수*/
	void timePrint(double time);
};

---

 

실습 문제

namespace _08.선형_자료_구조_실습
{
    public class Bullet
    {
        public static int BulletCount = 0;
        public Bullet() => ID = BulletCount++;
        ~Bullet() => BulletCount--;
        public int ID { get; private set; }
        public (float, float) Position { get; set; }
    }

    public class ObjectPool<T>
    {
        private LinkedList<T> pool;
        private Func<T> createFunc;
        private Action<T> resetAction;

        public ObjectPool(int size, Func<T> createFunc, Action<T> resetAction = null)
        {
            pool = new LinkedList<T>();
            this.createFunc = createFunc ?? throw new ArgumentNullException(nameof(createFunc));
            this.resetAction = resetAction;

            for (int i = 0; i < size; i++)
                pool.AddFirst(createFunc());
        }

        public T GetObject()
        {
            // ****** CODE HERE ******
            if (pool.Count > 0)
            {
                var obj = pool.First.Value;
                pool.RemoveFirst();
                return obj;
            }
            else
            {
                return createFunc();
            }
        }

        public void ReleaseObject(T obj)
        {
            // ****** CODE HERE ******
            resetAction?.Invoke(obj);
            pool.AddFirst(obj);
        }

        public int Count()
        {
            return pool.Count;
        }
    }

    // 구현 확인을 위한 코드입니다.
    class Program
    {
        static void Main(string[] args)
        {
            ObjectPool<Bullet> bulletPool = new ObjectPool<Bullet>(
                10,
                () => new Bullet(),
                bullet => { bullet.Position = (0, 0); }
            );

            // 현재 풀에 있는 객체 수를 출력합니다.
            Console.WriteLine($"Objects in pool: {bulletPool.Count()}");

            // 여러 개의 Bullet 객체를 풀에서 얻습니다.
            for (int i = 1; i <= 5; i++)
            {
                Bullet bullet = bulletPool.GetObject();
                bullet.Position = (i * 10.0f, i * 20.0f);
                Console.WriteLine($"Got bullet with ID: {bullet.ID}, Position: {bullet.Position}");
            }

            // 풀에서 객체를 다시 얻어서 출력했다가 반환합니다. 객체는 초기화된 상태여야 합니다.
            for (int i = 1; i <= 3; i++)
            {
                Bullet bullet = bulletPool.GetObject();
                Console.WriteLine($"Got bullet with ID: {bullet.ID}, Position: {bullet.Position}");
                bulletPool.ReleaseObject(bullet);
            }

            // 몇 개의 객체를 풀에 반환합니다.
            for (int i = 6; i <= 10; i++)
            {
                Bullet bullet = bulletPool.GetObject();
                bullet.Position = (i * 10.0f, i * 20.0f);
                bulletPool.ReleaseObject(bullet);
            }

            // 최종적으로 풀에 있는 객체 수를 출력합니다.
            Console.WriteLine($"Final objects in pool: {bulletPool.Count()}");
        }
    }
}

후기: 이미 LinkedList가 있어..? 나만 만들어 쓴거야??