[C#] 언제 List와 LinkedList를 사용해야합니까?

편집하다

이 답변에 대한 의견을 읽으십시오. 사람들은 내가 적절한 테스트를하지 않았다고 주장합니다. 나는 이것이 받아 들여서는 안된다는 데 동의합니다. 배우면서 몇 가지 테스트를 수행하고 공유하는 느낌이 들었습니다.

원래 답변 …

흥미로운 결과를 찾았습니다.

// Temporary class to show the example
class Temp
{
    public decimal A, B, C, D;

    public Temp(decimal a, decimal b, decimal c, decimal d)
    {
        A = a;            B = b;            C = c;            D = d;
    }
}

연결된 목록 (3.9 초)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.AddLast(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

목록 (2.4 초)

        List<Temp> list = new List<Temp>(); // 2.4 seconds

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.Add(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

본질적으로 데이터에만 액세스하더라도 훨씬 느립니다 !! 나는 linkedList를 사용하지 않는다고 말한다.

다음은 많은 인서트를 수행하는 또 다른 비교입니다 (목록 중간에 항목을 삽입 할 계획입니다)

연결 목록 (51 초)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            var curNode = list.First;

            for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
                curNode = curNode.Next;

            list.AddAfter(curNode, a); // Insert it after
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

목록 (7.26 초)

        List<Temp> list = new List<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.Insert(i / 2, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

삽입 할 위치에 대한 참조가있는 링크 된 목록 (.04 초)

        list.AddLast(new Temp(1,1,1,1));
        var referenceNode = list.First;

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            list.AddBefore(referenceNode, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

그래서 단지 당신이 여러 항목을 삽입 계획하고있는 경우 도 어딘가에는 다음 링크 된 목록을 사용하여 항목을 삽입 할 계획 곳의 레퍼런스를 가지고있다. 많은 항목을 삽입해야하기 때문에 삽입하려는 위치를 검색하면 시간이 걸리기 때문에 더 빠르지 않습니다.

답변