Click here to Skip to main content
15,892,737 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 357.1K   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.
# ================WINDOWS==================
# mkdir build; cd build;
# cmake -DCMAKE_BUILD_TYPE=Release -G "Visual Studio 11" ..
# msbuild List_vs_Vector.sln /p:Configuration=Release
# 
# and execute the example at: Release\list_vs_vector.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 (List_vs_Vector) 

IF(UNIX)
       MESSAGE("")
       MESSAGE("cmake for *NIX ")
       MESSAGE("if cmake finishes OK, do make")
       MESSAGE("then run ./list_vs_vector")
       MESSAGE("or run ./list_vs_vector_POD")
       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 List_vs_Vector.sln /p:Configuration=Release'")
       MESSAGE("then run 'Release\\list_vs_vector.exe'")
       MESSAGE("or run 'Release\\list_vs_vector_POD.exe'")
ENDIF(WIN32)

# =================
# Generic steps 
# =================
  include_directories(../src)
  # create the test executable
  add_executable(list_vs_vector ../src/main.cpp  ../src/g2_chrono.h ../src/linear_performance.h)

add_executable(list_vs_vector_POD ../src/main_POD_comparison.cpp)

target_link_libraries(list_vs_vector ${PLATFORM_LINK_LIBRIES})
target_link_libraries(list_vs_vector_POD ${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