#include <list>
#include <string>
#include <cctype>
using namespace std;
typedef unsigned int UINT32;
typedef unsigned short UINT16;
/************************************************************************/
/* 枚D定义: 性别 */
/************************************************************************/
typedef enum enumSexyType
{
SEXY_TYPE_MAN, //h?/span>
SEXY_TYPE_WOMAN, //x?/span>
SEXY_TYPE_GAY, //男同性恋
SEXY_TYPE_LESIBAIN, //奛_性恋
SEXY_TYPE_BUTT //未知性别
}ENUM_SEXY_TYPE;
/************************************************************************/
/* l构体定? ?nbsp; */
/************************************************************************/
typedef struct structMan
{
UINT32 sexType; // 性别 ENUM_SEXY_TYPE
UINT16 usAge; // q龄
string strName; // 名字
string strAddress; // 工作地址
bool operator < (const structMan &man) const
{
return usAge < man.usAge;
}
bool operator > (const structMan &man) const
{
return usAge > man.usAge;
}
structMan(UINT32 enumSexType = SEXY_TYPE_MAN,\
UINT16 usAge = 0 ,\
const string &refStrName = "" ,\
const string &refStrAddress = "")\
:
sexType(enumSexType),\
usAge(usAge) ,\
strName(refStrName),\
strAddress(refStrAddress)
{
//DO NOTHING HERE
};
}MAN;
//////////////////////////////////////////////////////////////////////////
typedef list<MAN> Family;
typedef list<MAN>::iterator FamilyIterator;
/*
* main函数 定义
*/
int main()
{
/* 初始?nbsp;*/
MAN stFather(SEXY_TYPE_MAN, 28, "倒霉熊老爸", "华ؓ(f)技术有限公?/span>");
MAN stMother(SEXY_TYPE_WOMAN, 27, "虄老妈", "郑州大学W二附属医院");
MAN stBaby (SEXY_TYPE_BUTT, 0, "天?/span>", "未知");
Family myFamily;
/* 依次存放到l(f)ist?nbsp; */
myFamily.push_back(stFather);
myFamily.push_back(stMother);
myFamily.push_back(stBaby);
/* 调用list的sort函数q行排序, 默认?x)用结构体重蝲?lt;? q行从小到大排序 */
myFamily.sort();
printf("按年龄从到大排?\n");
FamilyIterator it = myFamily.begin();
while(it != myFamily.end())
{
printf("姓名: %s \n", it->strName.c_str());
it++;
}
/* 调用模板函数 greater, 传入MANl构? q样?x)调用结构体重蝲?gt;? q行从大到小排序 */
greater<MAN> gt;
myFamily.sort(gt);
printf("\n按年龄从大到排?\n");
it = myFamily.begin();
while(it != myFamily.end())
{
printf("姓名: %s \n", it->strName.c_str());
it++;
}
return 0;
}
]]>
{
int num;
char name[10];
int age;
}Student,*pStudent;
void printName(pStudent pt)
{
printf("%s\n",pt->name);
return;
}
void main()
{
Student students[3]={{111, "liu", 18},
{222, "wang", 19},
{333, "zhao", 10}};
printName(students+2);
return;
}
2、选择
#include <stdio.h>
void main()
{
union
{
int k;
char i[2];
}*s, a;
s=&a;
s->i[0]=0x39;
s->i[1]=0x38;
printf("%x\n", a.k);
}
A.3839 B.3938 C.380039 D.不可预知
3?br>enum ENUM_A
{
X1,
Y1,
Z1=6,
A1,
B1
};
enum ENUM_A enumA=Y1;
enum ENUM_A enumB=B1;
enumA=_______
enumB=_______
4?br>VCHAR *pucCharArray[10][10];
typedef union unRec
{
ULONG ulIndex;
USHORT usLevel[6];
UCHAR ucDos;
}REC_S;
REC_S stMax, *pstMax;
四字节对齐时 sizeof(pucCharArray)=______
sizeof(stMax)=______
sizeof(*stMax)=______
5?br>typedef union unHead
{
UCHAR aucSrc[6];
struct tagContent
{
UCHAR ucFlag[3];
ULONG ulNext;
}Content;
}HEAD_S;
32位CPU,VC~译环境?
强制一字节寚w情况?h出sizeof(HEAD_S)
强制二字节对齐情况下,h出sizeof(HEAD_S)
强制四字节对齐情况下,h出sizeof(HEAD_S)
6?br>四字节对齐的情况?
typedef struct tagRec
{
long lA1;
char cA2;
char cA3;
long lA4;
long lA5;
}REC_S;
void main()
{
REC_S stMax;
printf("\r\n sizeof(stMax)=%d", sizeof(stMax));
return;
}
输出l果? sizeof(stMax)=______
7?br>typedef struct tagtest
{
unsigned char ucFlag;
unsigned long ulLen;
}TEST_S;
TEST_S test[10];
四字节对其时: sizeof(TEST_S)=_____ sizeof(test)=______
8?br>#pragma pack(4)
int main(int argc, char* argv[])
{
struct tagtest1
{
short a;
char d;
long b;
long c;
}
struct tagtest2
{
long b;
short c;
char d;
long a;
}
struct tagtest3
{
short c;
long b;
char d;
long a;
}
struct tagtest1 stT1;
struct tagtest2 stT2;
struct tagtest3 stT3;
printf("%d %d %d", sizeof(stT1), sizeof(stT2), sizeof(stT3));
return 0;
}
#pragma pack()
输出是______
9?br>typedef struct Head
{
VCHAR aucSrc[6];
VLONG ulType;
}HEAD_S;
在强制一字节对其的情况下,sizeof(HEAD_S)=____
在强制二字节对其的情况下,sizeof(HEAD_S)=____
10?br>union tagAAAA
{
struct
{
char ucFirst;
short usSecond;
char ucThird;
}half;
long lI;
}number;
struct tagBBBB
{
char ucFirst;
short usSecond;
char ucThird;
short usForth;
}half;
struct tagCCCC
{
struct
{
char ucFirst;
short usSecond;
char ucThird;
}half;
long lI;
};
在字节对其ؓ(f)1的情况下:
sizeof(union tagAAAA)=_____
sizeof(struct tagBBBB)=____
sizeof(struct tagCCCC)=____
字节寚w?的情况下:
sizeof(union tagAAAA)=_____
sizeof(struct tagBBBB)=____
sizeof(struct tagCCCC)=____
]]>
Daniel Robbins (drobbins@gentoo.org)
总裁Q首席执行官QGentoo TechnologiesQInc.
2001 q?7 ?/p>
在本pd文章中，(zhn)将学习(fn) RSA ?DSA 认证的工作原理，以及(qing)?jin)解如何正确讄无密码认证。在本系列的W一文章里QDaniel Robbins 主要介绍 RSA ?DSA 认证协议q向(zhn)展C如何在|络上应用这些协议?/blockquote>我们中有许多人把优秀?OpenSSHQ参见本文后面的参考资?/u>Q用作古老的
rsh命o(h)的替代品QOpenSSH 不仅是安全的而且是加密的。OpenSSH 更加吸引人的Ҏ(gu)之一是它能够使用Z一对互补的数字式密钥的 RSA ?DSA 认证协议来认证用戗RSA ?DSA 认证承诺不必提供密码p够同q程pȝ建立q接Q这是它的主要魅力之一。虽然这非常吸引人，但是 OpenSSH 的新用户们常总一U快速却不完善的方式配置 RSA/DSAQ结果虽然实C(jin)无密码登录，却也在此q程中开?jin)一个很大的安全漏洞?/p>什么是 RSA/DSA 认证Q?/span>
SSHQ特别是 OpenSSHQ完全免费的 SSH 的实玎ͼ(j)Q是一个不可思议的工兗类grshQ?code>sshdQ即telnet不同的是Q?code>ssh 的确很棒Q但q是有一?ssh-agent隐藏已经解密的专用密钥，q将介绍ssh-agent的前端，可以在不牺牲安全性的前提下提供许多便利。如果?zhn)一直想要掌?OpenSSH 更高U的认证功能的话Q那么就hl箋往下读吧?/p>RSA/DSA 密钥的工作原?/span>
下面从整体上_略的介l了(jin) RSA/DSA 密钥的工作原理。让我们从一U假想的情Ş开始，假定我们想用 RSA 认证允许一台本地的 Linux 工作站（UC localboxQ打开 remotebox 上的一个远E?shellQ?em>remotebox 是我们的 ISP 的一台机器。此刻，当我们试囄以应?RSA ?DSA 认证协议?/p>
% ssh drobbins@remotebox
drobbins@remotebox's password:此处我们看到的是
ssh׃(x)用安全密码认证协议，把我们的密码传送给 remotebox q行验证。但是，?ssh~省的认证方法相当安全，RSA ?DSA 认证却ؓ(f)我们开创了(jin)一些新的潜在的Z(x)?/p>但是Q与
sshd能够定位它而把它放在一个专门的文gQ~/.ssh/authorized_keysQ里Q我们就Z?RSA 认证d?remotebox 上做好了(jin)准备?/p>要用 RSA d的时候，我们只要?localbox 的控制台键入
ssh告诉 remotebox ?sshd?x)生成一个随机数Qƈ用我们先前拷贝过ȝ公用密钥对这个随机数q行加密。然后，ssh。接下来Q轮到我们的sshd得出l论Q既然我们持有匹配的专用密钥Q就应当允许我们d。因此，我们有匹配的专用密钥q一事实授权我们讉K remotebox?/p>两项注意事项
关于 RSA ?DSA 认证有两w要的注意事项。第一Ҏ(gu)我们的确只需要生成一对密钥。然后我们可以把我们的公用密钥拷贝到惌讉K的那些远E机器上Q它们都?x)根据我们的那把专用密钥q行恰当的认证。换句话_(d)我们q不需要ؓ(f)惌讉K?em> 每个pȝ都准备一对密钥。只要一对就_?jin)?/p>另一Ҏ(gu)意事Ҏ(gu)专用密钥不应落入其它人手?/em>。正是专用密钥授权我们访问远E系l，M拥有我们的专用密钥的人都?x)被授予和我们完? 相同的特权。如同我们不惌陌生人有我们的住处的钥匙一P我们应该保护我们的专用密钥以防未授权的用。在比特和字节的世界里，q意味着没有人是本来? 应该能读取或是拷贝我们的专用密钥的?/p>
ssh?ssh被设|成?jin)如果我们的密钥的文件权限允讔(dng)R我们之外的Q何hd密钥Q就打印Z条大大的警告消息。其ơ，在我们用ssh-keygen?x)要求我们输入一个密码短语。如果我们输入了(jin)密码短语Q?code>sshssh-keygen l探
讄 RSA 认证的第一步从生成一对公用／专用密钥对开始。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把专用密钥保存在此路径中，公用密钥存在紧临它的一个叫?identity.pub 的文仉?/p>q要h注意一?
ssh-keygen用这个密码短语加密了(jin)我们的专用密钥（~/.ssh/identityQ，以我们的专用密钥对于那些不知道q个密码短语的h变得毫无用处?/p>q求快速的折衷Ҏ(gu)
当我们指定密码短语时Q虽然这使得sshq接?drobbins@remotebox 帐户Ӟssh客户E序׃(x)处理其余的事情。虽然用我们的q程密码和?RSA 密码短语的机制完全不同，但实际上q是?x)提C我们输入一?#8220;保密的短?#8221;l?
# 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!
%q里是Zl常?x)被误导而导致追求快速的折衷Ҏ(gu)的地斏V有很多时候，仅仅是ؓ(f)?jin)不必输入密码，Z׃(x)创徏不加密的专用密钥。那L(fng)话，他们只要输入
# ssh drobbins@remotebox
Last login: Thu Jun 28 20:28:47 2001 from localbox.gentoo.org
Welcome to remotebox!
%然而，管q样很方便，但是在还没有完全理解q种Ҏ(gu)对安全性的影响Ӟ(zhn)不应该使用。如果有人在某一时刻闯入?localboxQ一把不加密的专用密钥得他们也自动有权讉K remotebox 以及(qing)其它所有用q把公用密钥配置q的pȝ?/p>
我知道?zhn)在想些什么。无密码认证Q虽然有点冒险，可看h的确很诱人。我完全同意。但是， q有更好的办法！L(fng)信我Q我向(zhn)展C如何既可以享受到无密码认证的好处，又不必牺牲专用密钥的安全性。在我的下一文章里Q我q将向?zhn)展示如何熟练的?
ssh-agent做好准备。下面是逐步的指对{?/p>RSA 密钥对的生成
要设|?RSA 认证Q我们需要执行生成公用／专用密钥对的一ơ性步骤。我们的输入如下Q?/p>
% ssh-keygen出现提示Ӟh受缺省的密钥位置Q典型的情况下是 ~/.ssh/identity 和存储公用密钥的 ~/.ssh/identity.pubQ，q提供给
ssh-keygen完成Q?zhn)?x)得到一把公用密钥和一把用密码短语加密的专用密钥?/p>RSA 公用密钥的安?/span>
接下来，我们需要把正在q行
% scp ~/.ssh/identity.pub drobbins@remotebox:׃ RSA 认证q没有完全设|好Q所以会(x)提示我们输入 remotebox 上的密码。请(zhn)照做。然后，d?remotebox q把公用密钥附加到文?~/.ssh/authorized_keys 上，如下所C：(x)
% 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现在Q配|过 RSA 认证以后Q当我们试图使用
% ssh drobbins@remotebox
Enter passphrase for key '/home/drobbins/.ssh/identity':
好哇QRSA 认证的配|完成了(jin)Q如果刚才没有提C?zhn)输入密码短语Q?zhn)可以试验一下以下几U情c(din)第一Q尝试通过输入
ssh只应?ssh 协议版本 1Q如果出于某U原因远E系l缺省设|的?DSA 认证的话Q可能会(x)要求q么做。如果不奏效的话Q请认(zhn)的 /etc/ssh/ssh_config 里没有写着q么一?DSA 密钥的生?/span>ssh协议的最新版本。目前所有的 OpenSSH 版本都应该既能?RSA 密钥又能使用 DSA 密钥。DSA 密钥以如下类g RSA 密钥的方式?OpenSSH ?
% ssh-keygen -t dsa又会(x)提示我们输入密码短语。输入一个安全的密码短语。还?x)提C我们输入保?DSA 密钥的位|。正常情况下Q缺省的 ~/.ssh/id_dsa ?~/.ssh/id_dsa.pub 可以了(jin)。在我们一ơ性生?DSA 密钥完成后，p把我们的 DSA 公用密钥安装到远E系l上M(jin)?/p>
DSA 公用密钥的安?/span>
DSA 公用密钥的安装又是几乎和 RSA 安装完全一栗对?DSAQ我们将要把 ~/.ssh/id_dsa.pub 文g拯?remoteboxQ然后把它附加到 remotebox 上的 ~/.ssh/authorized_keys2 文g。请注意q个文g的名字和 RSA ?authorized_keys 文g名不同。一旦配|完毕，输入我们?DSA 专用密钥的密码短语就应该能登录到 remoteboxQ而不需要我们输入在 remotebox 上真正的密码?/p>下一?/span>
此刻Q?zhn)应该已经可以使?RSA 或?DSA 认证?jin)，但是在每一ơ新q接Ӟ(zhn)仍需输入(zhn)的密码短语。在我的下一文章里Q我们将?x)?jin)解到如何使用keychainQ它是一个非常方便的ssh-agent比以前更可靠、更方便而且使用h更具味性。在此之前，请就q查阅下面列出的参考资料以使?zhn)能跟上进度?/p>
- 请务必访?OpenSSH 的开发主c(din)?br>
- L(fng)看最新的 OpenSSH 源代?tarball ?RPM?br>
- h?OpenSSH 常见问题解答?br>
- PuTTY 是用?Windows 机器的极好的
关于作?/span>Daniel Robbins 居住在美国新墨西哥州的阿?dng)布开克。他d?Gentoo LinuxQ这是一U用?PC 的高U?LinuxQ以?Portage pȝQ是用于 Linux 的下一代移植系l。他q是几本 Macmillan 出版的书c?Caldera OpenLinux Unleashed?em>SuSE Linux Unleashed ?Samba Unleashed 的投Eh。Daniel 自二q起就与计机l下?jin)不解之~，那时他最先接触的?Logo E序语言Qƈ沉h?Pac Man 游戏中。这也许是他至今仍担Q SONY Electronic Publishing/Psygnosis 首席囑Ş设计师的原因所在。Daniel 喜欢与妻?Mary 和新出生的女?Hadassah 一起共度时光。?zhn)可以通过 drobbins@gentoo.org ?Daniel 联系?br>
]]>
?-日志表，表结构如?
ID,F_LOGIN,MTime,ManageName qID是主?ID在我看来都是主键Q下文不再赘q?,F_LOGIN是用L(fng)登陆名羃写，MTime是用L(fng)操作旉QManageName是用h作的模块名称
?-用户表，l构如下:
ID,F_ORDER,F_LOGIN,F_USERNAME,F_DEPTNAME...,F_ORDER是用L(fng)序PF_LOGIN是用L(fng)登陆名羃?F_USERNAME是用L(fng)中文?F_DEPTNAME是用h在单位的名称
?-部门表，l构如下:
ID,F_DEPTORDER,F_DEPTNAME F_DEPTORDER是部门顺序号QF_DEPTNAME是部门名U?/p>
好了(jin)Q就是这么三个表Q客戯求根据统计用户对每个模块的用次敎ͼq要求按照部门顺序进行排?q且l计l果排除理帐号adminQ?br>怎么? 看到王以前的视图是Q?/p>
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
郁闷Q这试图看v来没什么问题啊Q但是一q行问题来?
考，如果部门A的用户都没有使用Q也是日志表里没有记录Q那么视NҎ(gu)׃?x)显C单位Q但是很明显q样不对Q我们需要没有用的单位昄ơ数?嘛，
我想办法不是明摆着的嘛Q把"INNER JOIN 部门?改ؓ(f)"RIGHT JOIN"部门表不ok?jin)么Q好Q改?
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
q行Q又郁闷Q怎么q是没有出现Q抓x腮半晌弄不明白，?j)想反正老子最不怕的是困难(最怕的是美x?sh)^_^),我一句一句来Q调试、调?l于发现问题所在：(x)
"WHERE (日志?F_login <> 'admin')"
当Right join以后Q没有操作的部门?x)在视图留下一条记录，而这条记录只包含部门表的信息Q用戯和日志表均ؓ(f)NULL,NULL是没有办法和'admin'比较的，也就是说NULL <> 'admin' q回的是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
q样不管怎么变，q所有用户和部门都是有的Q而且admin也过滤的Q但?...不对啊，怎么没有用户的单位用次数都很大啊，哦，原来是我用的count(*)
有问题，肯定得用sum函数啦。查查联Z书，最后定E如下：(x)
SELECT 用户?F_DEPTNAME,
SUM(CASE WHEN l计?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
l于搞定?jin)，万岁Q！不过CASE的用也分两U，一U是单CASE函数Q一U是CASE搜烦(ch)函数Q联Z书中关于when_expression 和Boolean_expression 写的很笼l，我的理解when_expression是一个|而Boolean_expression是一个判?嗯，写这个破东西也婆婆妈妈的写了(jin)半个时Q到此收W?br>
]]>
]]>
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:
- 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.
- 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()); - 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.
]]>