[問題] link, array, 比較取捨問題

[tropical72 (藍影)]

link 與 array 概念基本上從自修上的書大致上都有說到
整理一下我所吸收到的東西

(1) 新增移除資料：(double link == single?) > array

(2) 插入資料：(double link >= single link?) > array

(3) 做元素反排(reverse travel)：
    這點標題不知怎麼打比較好，我所參考的書似乎也沒強調這點。
    以array為例：
    int arr1[CNT], arr2[CNT];
    for(i=0; i<CNT; i++) arr2[CNT-i-1] = arr1[i];
    array 只要做 CNT 次即可。

    但若以 Single link 而言,每次都從 head 開始一直 travel 到後面,
    不論要不要 assign 給另一個 link,
    不就代表要花 CNT+(CNT-1)+....+1 = (1+CNT)*CNT/2 這麼久的時間？
    (雖有版友提出我的確沒想過 recursive 完成, 時間複雜度會改善嗎？)
    當然, double link 只要把 pre 和 next 對調就完成了(吧?)

(4) 交換(swap)：
    若array 形式為
    struct person{
       string name;
       int age;
       string address;
       ...
    };
    person array[CNT];

    在 swap 時 link 比較快，因不用逐一複製(當然可以用memcpy方式改善)
    但實做上比較複雜 (pre1, next1, pre2, next2 交換，要注意順序)

(5) 排序(sort)：
    這部份我所參考的書上也沒強調這點，所以我在想， link 不適合做排序的原因有二：

    (5.1) 要做排序的話，應是一開始建立資料時便用 "插入" 之方式建立結點，
          使整個 link 從頭到尾都是排好的狀態。

    (5.2) link 要取 index 比 array 麻煩

    以簡單的泡沫排序為例,
    for(i=0; i<CNT-1; i++){
        for(j=i+1; j<CNT; j++){
          if(arr[i]>arr[j]) swap(a[i], a[j]);
        }
    }
    但 link 要取得第i個、第j個元素，還是要重頭開始 travel,
    所以覺得 "單純用" link 做排序 - 超．慢！

(6) 若以排序做比較基準，我想 link 應該還是要再搭其它之資料結構
    (ex: tree) 速度上才會有所改善。

以上，是我對 link 與 array 比較上的認知，
若有補充或覺不妥之地方，請不吝指教。
另不知各位版友在考量要用 link 或 array，
是否有其它因素之考量？
最後謝謝各位先進耐心看完與指教。

ref:
(1) 演算法入門與進階 - 使用C語言(含資料結構), 初版,
    張紹勳 蔡志敏著, 松崗, 1991
(2) Data Sturctures and the Standard Template Library,
    William J.Collins, Mc Graw Hill, 2003

--
YouLoveMe() ? LetItBe() : LetMeFree();

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 180.177.76.142
→ akasan:新增移除插入那邊分析太少了一點 例如說新增刪除在頭還尾
→ akasan:排序那邊拿泡沫來分析有點low, 至少arrary 用Quick/Heap
→ akasan:LinkList用Insertion  要在無聊一點還可以考慮平行情況下
→ akasan:說無聊好像也還好畢竟多核心那麼便宜了
→ akasan:而且應該還要考量 Copy 成本之類的下去比較
→ tropical72:請問所謂的"無聊"指的是CPU使用率嗎？另Copy之成本是
→ tropical72:否能舉些例子？
→ akasan:無聊是指目前正常人寫程式應該不太會去平行化XD
→ akasan:Copy 成本大概就是指你 swap 中所指的東西
推 loveme00835:linked list 也能玩 QuickSort阿! :)
→ tropical72:我剛找了平行化的介紹,大致上是說一份code給二顆cpu跑
→ akasan:可以玩不代表適合玩阿XD
→ tropical72:(或稱多行緒較適合吧)請問link insert也能平行化？
→ loveme00835:其實非常適合, 也慢不了多少, 只是要下很多工夫
→ tropical72:l大的意思是..link適合拿來做sort,只是要花工夫的意思?
→ loveme00835:某些排序法在特定資料結構上要達到高效率很簡單, 但是
→ loveme00835:在其他資料結構上就很差, 所以必須作一點手腳, 但是這
→ loveme00835:個付出的代價會不會比你直接把資料結構換掉還高, 就要
→ loveme00835:看你的決定了
→ tropical72:非常感謝love00835解說,感激不盡！
→ yauhh:在講之前應該先說處理的是什麼資料,永遠保持排序的資料?