LinkedList链表基础资源-CSDN文库

5星 · 超过95%的资源需积分: 19 137 浏览量 2012-02-25 08:45:45 上传评论 1 收藏 46KB PDF 举报

### 链表基础知识 #### 引言链表是一种常用的数据结构，在计算机科学领域有着广泛的应用。本文档由Nick Parlante撰写，旨在为读者提供关于链表的基础知识和技术细节，包括解释、图表、示例代码和练习。文档不仅适合那些希望理解链表基本原理的人群，同时也适用于那些寻求真实应用中指针密集型代码实例的学习者。 #### 为什么学习链表？链表之所以值得学习，主要有两个原因：一方面，它们是一种实用的数据结构，可以在实际程序中使用；另一方面，通过链表的学习可以深入了解指针的工作机制。虽然在某些情况下，你可能永远不会在实际项目中直接使用链表，但理解和掌握链表背后的原理对于更好地使用指针至关重要。链表问题通常涉及算法和指针操作的结合，是初学者理解指针概念的理想场所。 #### 链表的定义与结构链表是一种线性数据结构，它不像数组那样在内存中连续存储元素，而是通过节点（Node）之间的链接来组织数据。每个节点包含两部分：一部分用于存储数据元素（称为数据域），另一部分则包含指向下一个节点的引用（称为指针域或链接域）。链表的基本类型包括单向链表（Singly Linked List）和双向链表（Doubly Linked List）。在单向链表中，每个节点只包含一个指向其后继节点的指针；而在双向链表中，除了包含指向后继节点的指针外，每个节点还包含一个指向前驱节点的指针，这使得双向链表支持更灵活的遍历方式。 #### 创建与操作链表创建链表通常包括以下几个步骤： 1. **初始化**：创建一个空的链表，通常通过一个头指针表示。 2. **插入节点**：在链表的不同位置插入新节点，例如头部插入、尾部插入或中间插入。 3. **删除节点**：根据特定条件删除链表中的节点。 4. **遍历链表**：访问链表中的每一个节点。 5. **查找节点**：基于特定条件搜索链表中的节点。 6. **反转链表**：改变链表节点的顺序。 #### 指针与内存管理为了深入理解链表，必须具备一定的指针和内存管理基础。在链表中，节点是由动态分配的内存块组成，因此需要通过指针来管理和操作这些内存块。理解如何正确地分配和释放内存，以及如何避免内存泄漏等问题，是学习链表不可或缺的一部分。 #### 实践与练习除了理论知识外，实践也是学习链表的重要组成部分。《链表问题》一文提供了18个不同难度级别的练习题，涵盖了链表操作的各个方面。通过解决这些问题，不仅可以巩固对链表基础知识的理解，还能提高解决问题的能力。 #### 结论链表作为一种重要的数据结构，对于程序员来说具有不可替代的价值。无论是作为实际项目中的解决方案，还是作为学习指针和内存管理的工具，链表都是必不可少的。通过本篇文章的学习，希望能够帮助读者建立起对链表及其应用场景的深刻认识，并为未来的学习和开发打下坚实的基础。

资源推荐

资源详情

资源评论

Linked List

Basics

Abstract

This document introduces the basic structures and techniques for building linked lists

with a mixture of explanations, drawings, sample code, and exercises. The material is

useful if you want to understand linked lists or if you want to see a realistic, applied

example of pointer-intensive code. A separate document, Linked List Problems

(http://cslibrary.stanford.edu/105/), presents 18 practice problems covering a wide range

of difficulty.

Linked lists are useful to study for two reasons. Most obviously, linked lists are a data

structure which you may want to use in real programs. Seeing the strengths and

weaknesses of linked lists will give you an appreciation of the some of the time, space,

and code issues which are useful to thinking about any data structures in general.

Somewhat less obviously, linked lists are great way to learn about pointers. In fact, you

may never use a linked list in a real program, but you are certain to use lots of pointers.

Linked list problems are a nice combination of algorithms and pointer manipulation.

Traditionally, linked lists have been the domain where beginning programmers get the

practice to really understand pointers.

Audience

The article assumes a basic understanding of programming and pointers. The article uses

C syntax for its examples where necessary, but the explanations avoid C specifics as

much as possible — really the discussion is oriented towards the important concepts of

pointer manipulation and linked list algorithms.

Other Resources

• Link List Problems (http://cslibrary.stanford.edu/105/) Lots of linked

list problems, with explanations, answers, and drawings. The "problems"

article is a companion to this "explanation" article.

• Pointers and Memory (http://cslibrary.stanford.edu/102/) Explains all

about how pointers and memory work. You need some understanding of

pointers and memory before you can understand linked lists.

• Essential C (http://cslibrary.stanford.edu/101/) Explains all the basic

features of the C programming language.

This is document #103, Linked List Basics, in the Stanford CS Education Library. This

and other free educational materials are available at http://cslibrary.stanford.edu/. This

document is free to be used, reproduced, or sold so long as this notice is clearly

reproduced at its beginning.

Here is a drawing of how the scores array might look like in memory. The key point is

that the entire array is allocated as one block of memory. Each element in the array gets

its own space in the array. Any element can be accessed directly using the [ ] syntax.

scores

index

23142

-3451

Once the array is set up, access to any element is convenient and fast with the [ ]

operator. (Extra for experts) Array access with expressions such as scores[i] is

almost always implemented using fast address arithmetic: the address of an element is

computed as an offset from the start of the array which only requires one multiplication

and one addition.

The disadvantages of arrays are...

1) The size of the array is fixed — 100 elements in this case. Most often this

size is specified at compile time with a simple declaration such as in the

example above . With a little extra effort, the size of the array can be

deferred until the array is created at runtime, but after that it remains fixed.

(extra for experts) You can go to the trouble of dynamically allocating an

array in the heap and then dynamically resizing it with realloc(), but that

requires some real programmer effort.

2) Because of (1), the most convenient thing for programmers to do is to

allocate arrays which seem "large enough" (e.g. the 100 in the scores

example). Although convenient, this strategy has two disadvantages: (a)

most of the time there are just 20 or 30 elements in the array and 70% of

the space in the array really is wasted. (b) If the program ever needs to

process more than 100 scores, the code breaks. A surprising amount of

commercial code has this sort of naive array allocation which wastes space

most of the time and crashes for special occasions. (Extra for experts) For

relatively large arrays (larger than 8k bytes), the virtual memory system

may partially compensate for this problem, since the "wasted" elements

are never touched.

3) (minor) Inserting new elements at the front is potentially expensive

because existing elements need to be shifted over to make room.

Linked lists have their own strengths and weaknesses, but they happen to be strong where

arrays are weak. The array's features all follow from its strategy of allocating the memory

for all its elements in one block of memory. Linked lists use an entirely different strategy.

As we will see, linked lists allocate memory for each element separately and only when

necessary.

Pointer Refresher

Here is a quick review of the terminology and rules for pointers. The linked list code to

follow will depend on these rules. (For much more detailed coverage of pointers and

memory, see Pointers and Memory, http://cslibrary.stanford.edu/102/).

• Pointer/Pointee A "pointer" stores a reference to another variable

sometimes known as its "pointee". Alternately, a pointer may be set to the

value NULL which encodes that it does not currently refer to a pointee. (In

C and C++ the value NULL can be used as a boolean false).

• Dereference The dereference operation on a pointer accesses its pointee.

A pointer may only be dereferenced after it has been set to refer to a

specific pointee. A pointer which does not have a pointee is "bad" (below)

and should not be dereferenced.

• Bad Pointer A pointer which does not have an assigned a pointee is

"bad" and should not be dereferenced. In C and C++, a dereference on a

bad sometimes crashes immediately at the dereference and sometimes

randomly corrupts the memory of the running program, causing a crash or

incorrect computation later. That sort of random bug is difficult to track

down. In C and C++, all pointers start out with bad values, so it is easy

to use bad pointer accidentally. Correct code sets each pointer to have a

good value before using it. Accidentally using a pointer when it is bad is

the most common bug in pointer code. In Java and other runtime oriented

languages, pointers automatically start out with the NULL value, so

dereferencing one is detected immediately. Java programs are much easier

to debug for this reason.

• Pointer assignment An assignment operation between two pointers like

p=q; makes the two pointers point to the same pointee. It does not copy

the pointee memory. After the assignment both pointers will point to the

same pointee memory which is known as a "sharing" situation.

• malloc() malloc() is a system function which allocates a block of

memory in the "heap" and returns a pointer to the new block. The

prototype for malloc() and other heap functions are in stdlib.h. The

argument to malloc() is the integer size of the block in bytes. Unlike local

("stack") variables, heap memory is not automatically deallocated when

the creating function exits. malloc() returns NULL if it cannot fulfill the

request. (extra for experts) You may check for the NULL case with

assert() if you wish just to be safe. Most modern programming systems

will throw an exception or do some other automatic error handling in their

memory allocator, so it is becoming less common that source code needs

to explicitly check for allocation failures.

• free() free() is the opposite of malloc(). Call free() on a block of heap

memory to indicate to the system that you are done with it. The argument

to free() is a pointer to a block of memory in the heap — a pointer which

some time earlier was obtained via a call to malloc().

What Linked Lists Look Like

An array allocates memory for all its elements lumped together as one block of memory.

In contrast, a linked list allocates space for each element separately in its own block of

memory called a "linked list element" or "node". The list gets is overall structure by using

pointers to connect all its nodes together like the links in a chain.

Each node contains two fields: a "data" field to store whatever element type the list holds

for its client, and a "next" field which is a pointer used to link one node to the next node.

Each node is allocated in the heap with a call to malloc(), so the node memory continues

to exist until it is explicitly deallocated with a call to free(). The front of the list is a

pointer to the first node. Here is what a list containing the numbers 1, 2, and 3 might look

like...

The Drawing Of List {1, 2, 3}

Stack Heap

A “head” pointer local to

BuildOneTwoThree() keeps

the whole list by storing a

pointer to the first node.

Each node

stores one

data element

(int in this

example).

Each node stores

one next pointer.

The overall list is built by connecting the

nodes together by their next pointers. The

nodes are all allocated in the heap.

The next field of

the last node is

NULL.

head

BuildOneTwoThree()

This drawing shows the list built in memory by the function BuildOneTwoThree() (the

full source code for this function is below). The beginning of the linked list is stored in a

"head" pointer which points to the first node. The first node contains a pointer to the

second node. The second node contains a pointer to the third node, ... and so on. The last

node in the list has its .next field set to NULL to mark the end of the list. Code can access

any node in the list by starting at the head and following the .next pointers. Operations

towards the front of the list are fast while operations which access node farther down the

list take longer the further they are from the front. This "linear" cost to access a node is

fundamentally more costly then the constant time [ ] access provided by arrays. In this

respect, linked lists are definitely less efficient than arrays.

Drawings such as above are important for thinking about pointer code, so most of the

examples in this article will associate code with its memory drawing to emphasize the

habit. In this case the head pointer is an ordinary local pointer variable, so it is drawn

separately on the left to show that it is in the stack. The list nodes are drawn on the right

to show that they are allocated in the heap.

The Empty List — NULL

The above is a list pointed to by head is described as being of "length three" since it is

made of three nodes with the .next field of the last node set to NULL. There needs to be

some representation of the empty list — the list with zero nodes. The most common

representation chosen for the empty list is a NULL head pointer. The empty list case is

the one common weird "boundary case" for linked list code. All of the code presented in

this article works correctly for the empty list case, but that was not without some effort.

When working on linked list code, it's a good habit to remember to check the empty list

case to verify that it works too. Sometimes the empty list case works the same as all the

cases, but sometimes it requires some special case code. No matter what, it's a good case

to at least think about.

剩余25页未读，继续阅读

评论收藏

内容反馈

darlingsun1988

2012-10-25

真的是STANFORD的资料，看了之后还有有些用处的，赞一个

stevemarbo

粉丝: 35
资源: 13

Linked List 链表基础

最新资源

Linked List 链表 基础

Linked List链表题型解题套路和模板【LeetCode刷题套路教程4】

Linked_List实现 链表

linked list 链表详解 源程序

常见的数据结构数组（Array）链表（Linked List）栈（Stack）

基于python的数据结构-链表Linked list

876.Middle of the Linked List 链表的中间结点【LeetCode单题讲解系列】

链表 Linked List【数据结构和算法入门4】

C#，单向链表（Simply Linked List）快速排序（Quick Sort）算法与源代码

陈越、何钦铭-数据结构作业6：Reversing Linked List链表翻转

List 对链表的操作

danlianbiao.rar_Linked list_链表

linklist 链表的基本操作c++

链表基础 学习文件

C#，双向链表（Doubly Linked List）归并排序（Merge Sort）算法与源代码

3 链表基础原理1

关于链表基础知识的详解

QT代码实现list链表结构

linked-list:简约链表

线性链表基础

Java链表（Linked List）基本原理与实现方法入门示例

链表_LINKLIST

链表的基本操作.docx

STL基础和链表基础

链表的使用

LinkedList

Lazy Linked-List(论文实现方法)

Lab10_doublylinkedlist_

doubly_linked_list.rar

linked list

前端大厂最新面试题-linked-list.docx

最新资源

Linked List 链表基础

Linked_List实现链表

linked list 链表详解源程序

链表基础学习文件