慢慢來

 說明：
         感謝luckycat 和陳梓瀚(vczh) 的留言。
         下面的代碼已經在Windows VC6/ Cygwin/ Suse Linux環境下編譯測試通過.

Daniel Robbins (drobbins@gentoo.org)
總裁／首席執行官，Gentoo Technologies，Inc.
2001 年 7 月

在本系列文章中，您將學習 RSA 和 DSA 認證的工作原理，以及了解如何正確設置無密碼認證。在本系列的第一篇文章里，Daniel Robbins 主要介紹 RSA 和 DSA 認證協議并向您展示如何在網絡上應用這些協議。

我們中有許多人把優秀的 OpenSSH（參見本文后面的參考資料）用作古老的 telnet 和 rsh 命令的替代品，OpenSSH 不僅是安全的而且是加密的。OpenSSH 更加吸引人的特性之一是它能夠使用基于一對互補的數字式密鑰的 RSA 和 DSA 認證協議來認證用戶。RSA 和 DSA 認證承諾不必提供密碼就能夠同遠程系統建立連接，這是它的主要魅力之一。雖然這非常吸引人，但是 OpenSSH 的新用戶們常常以一種快速卻不完善的方式配置 RSA/DSA，結果雖然實現了無密碼登錄，卻也在此過程中開了一個很大的安全漏洞。

什么是 RSA/DSA 認證？
SSH，特別是 OpenSSH（完全免費的 SSH 的實現），是一個不可思議的工具。類似于 telnet 或 rsh，ssh 客戶程序也可以用于登錄到遠程機器。所要求的只是該遠程機器正在運行 sshd，即 ssh 服務器進程。但是，與 telnet 不同的是，ssh 協議非常安全。加密數據流，確保數據流的完整性，甚至安全可靠的進行認證它都使用了專門的算法。

然而，雖然 ssh 的確很棒，但還是有一個 ssh 功能組件常常被忽略、被危險的誤用或者簡直就是被誤解。這個組件就是 OpenSSH 的 RSA/DSA 密鑰認證系統，它可以代替 OpenSSH 缺省使用的標準安全密碼認證系統。

OpenSSH 的 RSA 和 DSA 認證協議的基礎是一對專門生成的密鑰，分別叫做專用密鑰和公用密鑰。使用這些基于密鑰的認證系統的優勢在于：在許多情況下，有可能不必手工輸入密碼就能建立起安全的連接。

盡管基于密鑰的認證協議相當安全，但是當用戶并不完全了解這些簡化操作對安全性的影響，為了方便而使用某些簡化操作時，就會出現問題。本文中，我們 將詳細討論如何正確使用 RSA 和 DSA 認證協議，使我們不會冒任何不必要的安全性風險。在我的下一篇文章里，我將向您展示如何使用 ssh-agent 隱藏已經解密的專用密鑰，還將介紹 keychain，它是 ssh-agent 的前端，可以在不犧牲安全性的前提下提供許多便利。如果您一直想要掌握 OpenSSH 更高級的認證功能的話，那么就請您繼續往下讀吧。

RSA/DSA 密鑰的工作原理
下面從整體上粗略的介紹了 RSA/DSA 密鑰的工作原理。讓我們從一種假想的情形開始，假定我們想用 RSA 認證允許一臺本地的 Linux 工作站（稱作 localbox）打開 remotebox 上的一個遠程 shell，remotebox 是我們的 ISP 的一臺機器。此刻，當我們試圖用 ssh 客戶程序連接到 remotebox 時，我們會得到如下提示：

% ssh drobbins@remotebox
drobbins@remotebox's password:

此處我們看到的是 ssh 處理認證的缺省方式的一個示例。換句話說，它要求我們輸入 remotebox 上的 drobbins 這個帳戶的密碼。如果我們輸入我們在 remotebox 上的密碼，ssh 就會用安全密碼認證協議，把我們的密碼傳送給 remotebox 進行驗證。但是，和 telnet 的情況不同，這里我們的密碼是加密的，因此它不會被偷看到我們的數據連接的人截取。一旦 remotebox 把我們提供的密碼同它的密碼數據庫相對照進行認證，成功的話，我們就會被允許登錄，還會有一個 remotebox 的 shell 提示歡迎我們。雖然 ssh 缺省的認證方法相當安全，RSA 和 DSA 認證卻為我們開創了一些新的潛在的機會。

但是，與 ssh 安全密碼認證不同的是，RSA 認證需要一些初始配置。我們只需要執行這些初始配置步驟一次。之后，localbox 和 remotebox 之間的 RSA 認證就毫不費力了。要設置 RSA 認證，我們首先得生成一對密鑰，一把專用密鑰和一把公用密鑰。這兩把密鑰有一些非常有趣的性質。公用密鑰用于對消息進行加密，只有擁有專用密鑰的人才能對該消息進行解密。公用密鑰只能用于 加密，而專用密鑰只能用于對由匹配的公用密鑰編碼的消息進行解密。RSA（和 DSA）認證協議利用密鑰對的這些特殊性質進行安全認證，并且不需要在網上傳輸任何保密的信息。

要應用 RSA 或者 DSA 認證，我們要執行一步一次性的配置步驟。我們把公用密鑰拷貝到 remotebox。公用密鑰之所以被稱作是“公用的”有一個原因。因為它只能用于對那些給我們的消息進行 加密，所以我們不需要太擔心它會落入其它人手中。一旦我們的公用密鑰已經被拷貝到 remotebox 并且為了 remotebox 的 sshd 能夠定位它而把它放在一個專門的文件（~/.ssh/authorized_keys）里，我們就為使用 RSA 認證登錄到 remotebox 上做好了準備。

要用 RSA 登錄的時候，我們只要在 localbox 的控制臺鍵入 ssh drobbins@remotebox，就象我們常做的一樣?？蛇@一次，ssh 告訴 remotebox 的 sshd 它想使用 RSA 認證協議。接下來發生的事情非常有趣。Remotebox 的 sshd 會生成一個隨機數，并用我們先前拷貝過去的公用密鑰對這個隨機數進行加密。然后， sshd 把加密了的隨機數發回給正在 localbox 上運行的 ssh。接下來，輪到我們的 ssh 用專用密鑰對這個隨機數進行解密后，再把它發回給 remotebox，實際上等于在說：“瞧，我確實有匹配的專用密鑰；我能成功的對您的消息進行解密！”最后， sshd 得出結論，既然我們持有匹配的專用密鑰，就應當允許我們登錄。因此，我們有匹配的專用密鑰這一事實授權我們訪問 remotebox。

兩項注意事項
關于 RSA 和 DSA 認證有兩項重要的注意事項。第一項是我們的確只需要生成一對密鑰。然后我們可以把我們的公用密鑰拷貝到想要訪問的那些遠程機器上，它們都會根據我們的那把專用密鑰進行恰當的認證。換句話說，我們并不需要為想要訪問的 每個系統都準備一對密鑰。只要一對就足夠了。

另一項注意事項是專用密鑰不應落入其它人手中。正是專用密鑰授權我們訪問遠程系統，任何擁有我們的專用密鑰的人都會被授予和我們完全 相同的特權。如同我們不想讓陌生人有我們的住處的鑰匙一樣，我們應該保護我們的專用密鑰以防未授權的使用。在比特和字節的世界里，這意味著沒有人是本來就 應該能讀取或是拷貝我們的專用密鑰的。

ssh 的開發者們當然知道專用密鑰的重要性，而且他們已經在 ssh 和 ssh-keygen 里加入了一些防范措施，以防止我們的專用密鑰被濫用。首先，ssh 被設置成了如果我們的密鑰的文件權限允許除我們之外的任何人讀取密鑰，就打印出一條大大的警告消息。其次，在我們用 ssh-keygen 創建公用／專用密鑰對的時候，ssh-keygen 會要求我們輸入一個密碼短語。如果我們輸入了密碼短語，ssh-keygen 就會用該密碼短語加密我們的專用密鑰，這樣，即使專用密鑰被盜，對于那些碰巧不知道密碼短語的人而言，這把專用密鑰是毫無用處的。具備了這一知識后，讓我們看一下如何設置 ssh 以應用 RSA 和 DSA 認證協議。

ssh-keygen 細探
設置 RSA 認證的第一步從生成一對公用／專用密鑰對開始。RSA 認證是 ssh 密鑰認證的最初形式，因此 RSA 應該可以用于 OpenSSH 的所有版本，盡管這樣，我還是推薦您安裝可用的最近版本，在我寫這篇文章的時候是 openssh-2.9_p2。生成一對 RSA 密鑰的方法如下：

% ssh-keygen
Generating public/private rsa1 key pair.
Enter file in which to save the key (/home/drobbins/.ssh/identity): (hit enter)
Enter passphrase (empty for no passphrase): (enter a passphrase)
Enter same passphrase again: (enter it again)
Your identification has been saved in /home/drobbins/.ssh/identity.
Your public key has been saved in /home/drobbins/.ssh/identity.pub.
The key fingerprint is:
a4:e7:f2:39:a7:eb:fd:f8:39:f1:f1:7b:fe:48:a1:09 drobbins@localbox

當 ssh-keygen 要求輸入存放密鑰的缺省位置時，我們敲回車鍵接受缺省的 /home/drobbins/.ssh/identity。ssh-keygen 將把專用密鑰保存在此路徑中，公用密鑰就存在緊臨它的一個叫做 identity.pub 的文件里。

還要請您注意一下 ssh-keygen 還提示過我們輸入密碼短語。當時我們輸入了一個好的密碼短語（七位或者更多位難以預測的字符）。然后 ssh-keygen 用這個密碼短語加密了我們的專用密鑰（~/.ssh/identity），以使我們的專用密鑰對于那些不知道這個密碼短語的人將變得毫無用處。

追求快速的折衷方案
當我們指定密碼短語時，雖然這使得 ssh-keygen 保護我們的專用密鑰以防誤用，但是也帶來了一點小小的不便。現在，每當我們試圖用 ssh 連接到 drobbins@remotebox 帳戶時，ssh 都會提示我們輸入該密碼短語以便它能對我們的專用密鑰進行解密，并使用我們的專用密鑰進行 RSA 認證。此外，我們輸入的不是 remotebox 上 drobbins 帳戶的密碼，而是在本地機器上對專用密鑰進行解密所需要的密碼短語。一旦我們的專用密鑰被解密，我們的 ssh 客戶程序就會處理其余的事情。雖然使用我們的遠程密碼和使用 RSA 密碼短語的機制完全不同，但實際上還是會提示我們輸入一個“保密的短語”給 ssh。

# ssh drobbins@remotebox
Enter passphrase for key '/home/drobbins/.ssh/identity': (enter passphrase)
Last login: Thu Jun 28 20:28:47 2001 from localbox.gentoo.org 

Welcome to remotebox!

%

這里就是人們經常會被誤導而導致追求快速的折衷方案的地方。有很多時候，僅僅是為了不必輸入密碼，人們就會創建不加密的專用密鑰。那樣的話，他們只要輸入 ssh 命令，立刻就會通過 RSA（或是 DSA）認證并登錄。

# ssh drobbins@remotebox
Last login: Thu Jun 28 20:28:47 2001 from localbox.gentoo.org 

Welcome to remotebox!

%

然而，盡管這樣很方便，但是在還沒有完全理解這種方法對安全性的影響時，您不應該使用。如果有人在某一時刻闖入了 localbox，一把不加密的專用密鑰使得他們也自動有權訪問 remotebox 以及其它所有用這把公用密鑰配置過的系統。

我知道您在想些什么。無密碼認證，雖然有點冒險，可看起來的確很誘人。我完全同意。但是， 還有更好的辦法！請相信我，我將向您展示如何既可以享受到無密碼認證的好處，又不必犧牲專用密鑰的安全性。在我的下一篇文章里，我還將向您展示如何熟練的使用 ssh-agent（正是它最先使得安全無密碼認證成為可能）?，F在，讓我們通過設置 RSA 和 DSA 認證為使用 ssh-agent 做好準備。下面是逐步的指導。

RSA 密鑰對的生成
要設置 RSA 認證，我們需要執行生成公用／專用密鑰對的一次性步驟。我們的輸入如下：

% ssh-keygen

出現提示時，請接受缺省的密鑰位置（典型的情況下是 ~/.ssh/identity 和存儲公用密鑰的 ~/.ssh/identity.pub），并提供給 ssh-keygen 一個安全的密碼短語。一旦 ssh-keygen 完成，您將會得到一把公用密鑰和一把用密碼短語加密的專用密鑰。

RSA 公用密鑰的安裝
接下來，我們需要把正在運行 sshd 的遠程系統設置成使用我們的公用 RSA 密鑰進行認證。典型情況下，我們通過象下面這樣把公用密鑰拷貝到遠程系統完成這一步：

% scp ~/.ssh/identity.pub drobbins@remotebox:

由于 RSA 認證還沒有完全設置好，所以會提示我們輸入 remotebox 上的密碼。請您照做。然后，登錄到 remotebox 并把公用密鑰附加到文件 ~/.ssh/authorized_keys 上，如下所示：

% ssh drobbins@remotebox
drobbins@remotebox's password: (enter password)
Last login: Thu Jun 28 20:28:47 2001 from localbox.gentoo.org 

Welcome to remotebox!

% cat identity.pub >> ~/.ssh/authorized_keys
% exit

現在，配置過 RSA 認證以后，當我們試圖使用 ssh 連接到 remotebox 時，應該會提示我們輸入 RSA 密碼短語（而不是我們的密碼）。

% ssh drobbins@remotebox
Enter passphrase for key '/home/drobbins/.ssh/identity': 

好哇，RSA 認證的配置完成了！如果剛才沒有提示您輸入密碼短語，您可以試驗一下以下幾種情況。第一，嘗試通過輸入 ssh -1 drobbins@remotebox 登錄。它會讓 ssh 只應用 ssh 協議版本 1，如果出于某種原因遠程系統缺省設置的是 DSA 認證的話，可能會要求這么做。如果不奏效的話，請確認您的 /etc/ssh/ssh_config 里沒有寫著這么一行 RSAAuthentication no。如果有的話，請您在前面加上一個“#”把這行注釋掉。另外，還可以試著同 remotebox 的系統管理員聯絡，核實一下在他們那一端已經啟用了 RSA 認證，并且 /etc/ssh/sshd_config 里的設置是正確的。

DSA 密鑰的生成
ssh 協議的版本 1 使用的是 RSA 密鑰，而 DSA 密鑰卻用于協議級 2，這是 ssh 協議的最新版本。目前所有的 OpenSSH 版本都應該既能使用 RSA 密鑰又能使用 DSA 密鑰。DSA 密鑰以如下類似于 RSA 密鑰的方式使用 OpenSSH 的 ssh-keygen 生成：

% ssh-keygen -t dsa

又會提示我們輸入密碼短語。輸入一個安全的密碼短語。還會提示我們輸入保存 DSA 密鑰的位置。正常情況下，缺省的 ~/.ssh/id_dsa 和 ~/.ssh/id_dsa.pub 就可以了。在我們一次性生成 DSA 密鑰完成后，就該把我們的 DSA 公用密鑰安裝到遠程系統上去了。

DSA 公用密鑰的安裝
DSA 公用密鑰的安裝又是幾乎和 RSA 安裝完全一樣。對于 DSA，我們將要把 ~/.ssh/id_dsa.pub 文件拷貝到 remotebox，然后把它附加到 remotebox 上的 ~/.ssh/authorized_keys2 文件。請注意這個文件的名字和 RSA 的 authorized_keys 文件名不同。一旦配置完畢，輸入我們的 DSA 專用密鑰的密碼短語就應該能登錄到 remotebox，而不需要我們輸入在 remotebox 上真正的密碼。

下一篇
此刻，您應該已經可以使用 RSA 或者 DSA 認證了，但是在每一次新連接時，您仍需輸入您的密碼短語。在我的下一篇文章里，我們將會了解到如何使用 ssh-agent，它確實是一個很不錯的系統，不僅允許我們不提供密碼就建立連接，而且還使我們的專用密鑰可以在磁盤上保持加密狀態。我還將介紹 keychain，它是一個非常方便的 ssh-agent 前端，可以使 ssh-agent 比以前更可靠、更方便而且使用起來更具趣味性。在此之前，請就近查閱下面列出的參考資料以使您能跟上進度。

參考資料

• 請務必訪問 OpenSSH 的開發主頁。
  
  
• 請看看最新的 OpenSSH 源代碼 tarball 和 RPM。
  
  
• 請查閱 OpenSSH 常見問題解答。
  
  
• PuTTY 是用于 Windows 機器的極好的 ssh 客戶程序。
  
  
• 您會發現 O'Reilly 的 SSH, The Secure Shell: The Definitive Guide 會對您有所幫助。作者的網站上有關于這本書、常見問題解答、新聞和最新信息。
  
  
• 請閱讀 developerWorks 上的 Addressing security issues in Linux 以獲得關于數據加密和許多其它安全性論題的概述。
  
  
• 請瀏覽 developerWorks 上更多的 Linux 參考資料。
  
  
• 請瀏覽 developerWorks 上 更多的開放源代碼參考資料。

今日見小王同志眉頭微皺，心想這兄臺必然遇到難題，遂問其故。果不其然，他在通過日志表統計用戶使用情況時創建試圖屢屢失敗。
我以前也沒有做過類似的SQL,但又想這實現總該不難，于是拿來分析，情況如下:
表1-日志表，表結構如下:
ID,F_LOGIN,MTime,ManageName 這ID是主鍵(ID在我看來都是主鍵，下文不再贅述),F_LOGIN是用戶的登陸名縮寫，MTime是用戶的操作時間，ManageName是用戶操作的模塊名稱
表2-用戶表，結構如下:
ID,F_ORDER,F_LOGIN,F_USERNAME,F_DEPTNAME...,F_ORDER是用戶的順序號，F_LOGIN是用戶的登陸名縮寫,F_USERNAME是用戶的中文名,F_DEPTNAME是用戶所在單位的名稱
表3-部門表，結構如下:
ID,F_DEPTORDER,F_DEPTNAME F_DEPTORDER是部門順序號，F_DEPTNAME是部門名稱。

好了，就是這么三個表，客戶要求根據統計用戶對每個模塊的使用次數，并要求按照部門順序進行排序,并且統計結果排除管理帳號admin：
怎么辦? 看到小王以前的視圖是：

SELECT  用戶表.F_DEPTNAME, COUNT(*)
      AS count, 部門表.F_ORDER
FROM 日志表 INNER JOIN
      用戶表 ON
      日志表.F_login = 用戶表.F_LOGIN INNER JOIN
      部門表 ON
      用戶表.F_DEPTNAME = 部門表.F_DEPATNAME
WHERE (日志表.F_login <> 'admin')
GROUP BY 用戶表.F_DEPTNAME,
      部門表.F_NO
ORDER BY 部門表.F_NO

郁悶，這試圖看起來沒什么問題啊，但是一運行問題就來了:
考，如果部門A的用戶都沒有使用，也就是日志表里沒有記錄，那么視圖里根本就不會顯示該單位，但是很明顯這樣不對，我們需要沒有使用的單位顯示次數為0嘛，
我想辦法不是明擺著的嘛，把"INNER JOIN 部門表"改為"RIGHT JOIN"部門表不就ok了么，好，改變:

SELECT  用戶表.F_DEPTNAME, COUNT(*)
      AS count, 部門表.F_ORDER
FROM 日志表 INNER JOIN
      用戶表 ON
      日志表.F_login = 用戶表.F_LOGIN RIGHT JOIN
      部門表 ON
      用戶表.F_DEPTNAME = 部門表.F_DEPATNAME
WHERE (日志表.F_login <> 'admin')
GROUP BY 用戶表.F_DEPTNAME,
      部門表.F_NO
ORDER BY 部門表.F_NO

運行，又郁悶，怎么還是沒有出現，抓耳撓腮半晌弄不明白，心想反正老子最不怕的就是困難(最怕的是美女放電^_^),我一句一句來，調試、調試,終于發現問題所在：
"WHERE (日志表.F_login <> 'admin')"
當Right join以后，沒有操作的部門會在視圖留下一條記錄，而這條記錄只包含部門表的信息，用戶表和日志表均為NULL,NULL是沒有辦法和'admin'比較的，也就是說NULL <> 'admin' 返回的是false,怎么辦?調整視圖join的次序，如下:
SELECT  用戶表.F_DEPTNAME, COUNT(*)
      AS count, 部門表.F_ORDER
FROM 用戶表 INNER JOIN
      部門表 ON
      用戶表.F_DEPTNAME = 部門表.F_DEPATNAME LEFT JOIN
      日志表 ON
      日志表.F_login = 用戶表.F_LOGIN
WHERE (用戶表.F_login <> 'admin')
GROUP BY 用戶表.F_DEPTNAME,
      部門表.F_NO
ORDER BY 部門表.F_NO

這樣不管怎么變，這所有用戶和部門都是有的，而且admin也過濾的，但是....不對啊，怎么沒有用戶的單位使用次數都很大啊，哦，原來是我用的count(*)
有問題，肯定得用sum函數啦。查查聯機叢書，最后定稿如下：
SELECT  用戶表.F_DEPTNAME,
SUM(CASE WHEN 統計表.F_login IS NULL THEN 0 ELSE 1 END) as count,
部門表.F_ORDER
FROM 用戶表 INNER JOIN
      部門表 ON
      用戶表.F_DEPTNAME = 部門表.F_DEPATNAME LEFT JOIN
      日志表 ON
      日志表.F_login = 用戶表.F_LOGIN
WHERE (用戶表.F_login <> 'admin')
GROUP BY 用戶表.F_DEPTNAME,
      部門表.F_NO
ORDER BY 部門表.F_NO

終于搞定了，萬歲??！不過CASE的使用也分兩種，一種是簡單CASE函數，一種是CASE搜索函數，聯機從書中關于when_expression 和Boolean_expression 寫的很籠統，我的理解when_expression就是一個值，而Boolean_expression是一個判斷,嗯，寫這個破東西也婆婆媽媽的寫了半個小時，到此收筆。

copied from Pankaj Kumar's Weblog

The trade-offs in using java.util.ArrayList and java.util.LinkedList should be straight-forward, shouldn't it? At least this is what I used to think till today. But then most of my thinking around these datastructures were formed during college days, when C was the hottest language and Java and its Collection classes just didn't exist.

Not surprisingly, it is natural for me to think of arrays as fixed size containers, where elements can be accessed at random location through O(1) operation (ie; in constant time) and insertion/deletion in the middle are O(N) operations (ie; could take time proportional to the size of the array) and hence, are better avoided. In contrast, a linked list can grow in size, access of its head or tail and insertion/deletion in the middle are all O(1) operations (assuming that you have pointer to an adjacent element).

It is possible get around the fixed size limitation of arrays by writing a wrapper which will allocate a new array, copy the elements of the old array into the new one and then discard the old one (BTW, this is what ArrayList does). Still, the basic arrays remain a datastructure for collections of fixed size. In contrast, a linked list consists of nodes with 'pointers' to the next and previous node in the list. So, adding or removing a node is simply a matter of reassigning the pointers. Of course, this implies linear time for traversing upto an indexed node, starting from beginning or end. This simple model is very handy in deciding when to use an array and when to use a linked list.

In Java, the ArrayList and LinkedList classes provide a uniform interface to both these datastructures and hence, destroy this simple conceptual model, so necessary to make judicious implementation decisions, in impressionable young minds of many Java programmers. Let me further elaborate this with my recent own experience.

Today, while going over a graph traversal code, I was somewhat alarmed by the generous use of ArrayLists. This code was written by someone who perhaps had learnt programming with Java. As hinted earlier, both ArrayList and LinkedList implement List interface and support similar operations. An ArrayList can grow dynamically and allows insertion/deletion of elements. A LinkedList also allows access of elements through an index, exactly the same way as an ArrayList. This is all fine. However, the problem is that the apparent similarity in the API hides the widely different memory and time costs of these datastructures for different kinds of operations, luring the unwary to use them in dangerous ways:

1. An empty ArrayList takes two to three times more memory than an empty LinkedList (because ArrayList would typically preallocate memory). This becomes important if you plan to keep an adjacency list of nodes for each node in the graph and you know beforehand that the nodes will have at most one or two adjacent nodes and the total number of nodes in the graph can be quite large.

2. The following straight-forward loop to iterate over all elements of a list
   
   
   ??for (int i = 0; i < list.size(); i++)
   ????doSomething(list.get(i));
   
   
   works great for an ArrayList but will cause serious performance problems for a LinkedList. Can you guess why? The right way to iterate over a LinkedList is:
   
   
   ??ListIterator li = list.listIterator(0);
   ??while (li.hasNext())
   ????doSomething(li.next());
   
   
   

3. Although both ArrayList and LinkedList allow insertion/deletion in the middle through similar operations (ie; by invoking add(int index) or remove(index)), these operations do not offer you the advantage of O(1) insertion/deletion for a LinkedList. For that, you must work through a ListIterator.
   

While researching on this topic, I did find a couple of good articles on the Web:

• JDC Tech Tip article on Using ArrayList/LinkedList. Good coverage of the topic. Worth reading if you want to know more about performance tradeoffs.
  
• joustlog entry titled LinkedList vs. ArrayList performance tests and subsequent clarification. This entry is more focussed in scope, pointing out the fact that addition as the end is faster for ArrayList than for LinkedList. The only thing I would like to add is that addition at the end of a LinkedList is always O(1) whereas addition at the end of an ArrayList is amortized O(1), meaning if you do M at-the-end additions then the total cost will be proportional to M. This is due to the fact that the underlying array may have to be grown (a new one to be allocated, old one to be copied and discarded) when the capacity is reached. However, I can understand that a normal at-the-end addition (ie; not involving resizing of the underlying array) will be faster for ArrayList (compared to LinkedList).
  

I am not advocating either ArrayList or LinkedList, though it can be justifiably argued that the use of ArrayList is better suited in many more programming scenarios, and I have no contention with that. The point I am making is that the sameness of the API makes it easy for programmers to assume that these can be used interchangeably. Nothing can be farther from truth. They are distinct datastructures, each optimized for certain kinds of operations and domain of applicability. And a good programmer should be aware of the distinction. The API exposed by the above mentioned Java classes blur this distinction. In my opinion, this is one of those areas where implementation hiding behind a common, easy-to-use interface (think of List interface that both ArrayList and LinkedList implement) may not be in the best interest of the primary user of these classes.