Click here to Skip to main content
15,892,005 members
Articles / Containers

Number crunching: Why you should never, ever, EVER use linked-list in your code again

Rate me:
Please Sign up or sign in to vote.
4.86/5 (76 votes)
21 Aug 2012Public Domain28 min read 356.9K   1K   99  
Most programming resources are wrong when comparing linked-list to vector. Here you can read and understand how they are wrong and why linked-list is (mostly) to be avoided.
#Ideone.com examples to be compiled and run
# on your computer
#===================
#ideone_62Emz.cpp : Linear insert of random elements in sorted order
#                   [http://ideone.com/62Emz]
#
#
#ideone_tLUeK.cpp: Sort comparison vector vs list [http://ideone.com/tLUeK]
#
#
#ideone_u5wbd.java: Similar to the linear insertion of random elements in 
#                   order but with JAVA code. [http://ideone.com/u5wbd]
#          The java example is not compiled here but can easily be done manually
#          javac ideone_u5wbd.java
#          java ideone_u5wb
#
#ideone_XprUU.cpp: "Smart" linked-list. Saving of last insertion position pointer
#                  to possibly avoid traversing unnecessarily long distance.
#                  [ideone.com/XprUU]
#
#
#ideone_W9vpT.cpp: Linear insert of random POD elements. The test is done with
#                  varying POD sizes. On [ideone.com/W9vpT] the test will
#                  timeout before finishing for the largest POD size (256 bytes).
#
#
# ================WINDOWS==================
# mkdir build; cd build;
# cmake -DCMAKE_BUILD_TYPE=Release -G "Visual Studio 11" ..
# msbuild ideone_examples.sln /p:Configuration=Release
# 
# and execute the example at: Release\ideone_xxxx.exe
#
# IMPORTANT: If you do not do the steps above you might 
#            get debug and not release version. The performance
#            difference between them are HUGE!
#
# ================LINUX==================
# mkdir build; cd build;
# cmake; make
# 
# IMPORTANT: If the performance difference between linked-list and vector is small
#            or if the performance result is not at all what you expected then please
#            verify that you are using RELEASE and not DEBUG version
#            I.e. call "make" with "make VERBOSE=1"
#                 this will show what make settings you have. 
#                 03 should be used for this performance test
cmake_minimum_required (VERSION 2.8)
ENABLE_LANGUAGE(CXX)
set(CMAKE_BUILD_TYPE Release)
project (ideone_examples) 

IF(UNIX)
       MESSAGE("")
       MESSAGE("cmake for *NIX ")
       MESSAGE("if cmake finishes OK, do make")
       MESSAGE("then run the ./ideone_* examples")
       MESSAGE("")
       set(CMAKE_CXX_FLAGS "-Wall -Wunused -std=c++0x")
ENDIF(UNIX)

IF(WIN32)   	
       MESSAGE("")
       MESSAGE("")
       MESSAGE("cmake for Visual Studio 2011")
       MESSAGE("if cmake finishes OK, do 'msbuild ideone_examples.sln /p:Configuration=Release'")
      MESSAGE("then run the ./ideone_* examples")
 ENDIF(WIN32)

# =================
# Generic steps 
# =================
add_executable(ideone_62Emz ../src/ideone_62Emz.cpp) 
add_executable(ideone_tLUeK ../src/ideone_tLUeK.cpp)
add_executable(ideone_W9vpT ../src/ideone_W9vpT.cpp)
add_executable(ideone_XprUU ../src/ideone_XprUU.cpp)
#
# Java has to be run manually
# javac ideone_u5wbd.java
# java ideone_u5wbd

target_link_libraries(ideone_62Emz ${PLATFORM_LINK_LIBRIES})
target_link_libraries(ideone_62Emz ${PLATFORM_LINK_LIBRIES})
target_link_libraries(ideone_W9vpT ${PLATFORM_LINK_LIBRIES})
target_link_libraries(ideone_W9vpT ${PLATFORM_LINK_LIBRIES})




By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under A Public Domain dedication


Written By
Software Developer (Senior) LogRhythm
United States United States
Enjoying Colorado! Family and intense software development.

Kjell is a driven developer with a passion for software development. His focus is on coding, boosting software development, improving development efficiency and turning bad projects into good projects.

Kjell was twice national champion in WUKO and semi-contact Karate and now he focuses his kime towards software engineering, everyday challenges and moose hunting while not being (almost constantly) amazed by his daughter and sons.

Comments and Discussions