什么是链表?链表与数组的区别?


本文摘自PHP中文网,作者零下一度,侵删。

链表的相关知识整理

什么是链表

  链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

链表与数组的区别

  回忆下数组的概念 ,所谓数组,是相同数据类型的元素按一定顺序排列的集合。根据概念我们可以知道数组在内存中连续,链表不连续;由于不同的存储方式导致数组静态分配内存,链表动态分配内存,数组元素在栈区,链表元素在堆区;由于数组在内存中连续,我们可以利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);但是由于数组的连续性数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。总结一下,数组和链表的区别如下
  1.数组静态分配内存,链表动态分配内存
  2.数组在内存中连续,链表不连续
  3.数组元素在栈区,链表元素在堆区
  4.数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);
  5.数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。

C#实现链表的基本操作

  以单链表为例,根据链表的定义我们先定义链表节点的数据结构

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

public class Node<T>

{

    private T data;

    private Node<T> next;

 

    //有参构造函数

    //主要用例实例化需要处理的节点用

    public Node(T item, Node<T> next)

    {

        data = item;

        this.next = next;

    }

 

    //无参构造函数,用例实例化Node节点

    public Node()

    {

        data = default(T);

        next = null;

    }

 

    public Node<T> Next

    {

        get { return next; }

        set { this.next = value; }

    }

 

    public T Data

    {

        get { return data; }

        set { this.data = value; }

    }

}

  接下来我们来实现链表的操作,构造一个链表,在构造链表里我们定一个头结点的对象,头结点是个很有用的节点,在后续代码中就可以慢慢体会到

1

2

3

4

5

6

7

8

9

10

public class MyLinkList<T>

{

   public Node<T> Head { get; set; }

 

    //构造器 

    public MyLinkList()

    {

        Head = null;

    }

}

  1.求链表的长度,思路:从头结点向后访问,直到最后一个节点,代码如下

1

2

3

4

5

6

7

8

9

10

11

public int Length()

 {

     var p = Head;

     int len = 0;

     while (p != null)

     {

         ++len;

         p = p.Next;

     }

     return len;

 }

  2.清空链表,这个就比较奥简单了,直接将头结点置为null 即可,代码如下

1

2

3

4

public void Clear()

{

    Head = null;

}

  3.同理判断链表是否为空也要用的头结点

1

2

3

4

5

6

7

8

9

10

11

public bool IsEmpty()

{

    if (Head == null)

    {

        return true;

    }

    else

    {

        return false;

    }

}

  4.在链表的末尾添加新元素,添加新元素,需要先判断链表是否为空,如果为空我们要给头结点赋值,如果不为空需要修改最后一个节点的next指向,代码如下

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

public void Append(T item)

 {

 

     if (Head == null)

     {

         Head = new Node<T>(item, null);

         return;

     }

     var p = new Node<T>();

     p = Head;

     while (p.Next != null)

     {

         p = p.Next;

     }

     p.Next = new Node<T>(item, null);

 }

  5.在单链表的第i个结点的位置前插入一个指定结点,首先需要找到插入的位置,然后修改相邻节点的指向即可, 代码如下

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

public void Insert(T item, int i)

{

 

    if (IsEmpty() || i < 1 || i > GetLength())

    {

        return;

    }

    //如果在第一个位置插入 则只需要将该节点的next 指向head即可

    if (i == 1)

    {

        var first = new Node<T>(item, null);

        first.Next = Head;

        Head = first;

        return;

    }

 

    var p = new Node<T>();

    p = Head;

    var left = new Node<T>();

    var right = new Node<T>();

    int j = 1;

    while (p.Next != null && j < i)

    {

        left = p;

        right = p.Next;

        ++j;

    }

    var q = new Node<T>(item, null);

    left.Next = q;

    q.Next = right;

}

  6.删除指定节点,先找到要删除的前一个结点,然后修改该结点的next指向即可 代码略。。。。

?  7.链表还有删除、获取、查找等操作,基本思想都是一样的,就不一一介绍了

链表相关的经典题目

  1. 求单链表中结点的个数
  2. 将单链表反转
  3. 查找单链表中的倒数第K个结点(k > 0)
  4. 查找单链表的中间结点
  5. 从尾到头打印单链表
  6. 已知两个单链表pHead1 和pHead2 各自有序,把它们合并成一个链表依然有序
  7. 判断一个单链表中是否有环
  8. 判断两个单链表是否相交
  9. 求两个单链表相交的第一个节点
  10. 已知一个单链表中存在环,求进入环中的第一个节点
  11. 给出一单链表头指针pHead和一节点指针pToBeDeleted,O(1)时间复杂度删除节点pToBeDeleted

好了就撸到这里,题目是剑指offer里的题目,大家可以解答下,有问题联系我

  

以上就是什么是链表?链表与数组的区别?的详细内容!

相关阅读 >>

契约类相关的序列化与反序列化实例详解

什么是链表?链表与数组的区别?

总结.net平台上一些常用的框架

c# 一些面试试题的实例教程

有关mvc异常情况的相关处理

asp .net 面试题及答案分享

分享一些平时收藏和应用的开源代码

更多相关阅读请进入《整理》频道 >>




打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在

评论

管理员已关闭评论功能...