计算机专业面试常见数据结构基础之链表操作

一、概述

在计算机专业面试中，数据结构是基础中的基础。链表作为数据结构中的一种，是面试官经常问到的之一。本文将围绕链表的操作展开，帮助面试者更好地准备面试。

二、链表的基本概念

链表是一种非线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表具有特点：

1. 顺序存储：链表中的节点在内存中不一定连续，但按照插入顺序排列。

2. 动态存储：链表可以根据需要动态地增加或删除节点。

3. 不支持随机访问：链表中节点的访问需要从头节点开始，依次遍历。

三、链表的操作

1. 创建链表

java

public class Node {

int data;

Node next;

public Node(int data) {

this.data = data;

this.next = null;

}

}

public class LinkedList {

Node head;

public LinkedList() {

this.head = null;

}

// 创建链表

public void createList(int[] arr) {

if (arr == null || arr.length == 0) {

return;

}

Node prev = null;

for (int i = 0; i < arr.length; i++) {

Node node = new Node(arr[i]);

if (prev == null) {

head = node;

} else {

prev.next = node;

}

prev = node;

}

}

}

2. 遍历链表

java

public void traverseList() {

Node node = head;

while (node != null) {

System.out.print(node.data + " ");

node = node.next;

}

System.out.println();

}

3. 插入节点

java

public void insertNode(int data, int position) {

Node newNode = new Node(data);

if (position == 0) {

newNode.next = head;

head = newNode;

return;

}

Node current = head;

int i = 0;

while (current != null && i < position – 1) {

current = current.next;

i++;

}

if (current == null) {

System.out.println("插入位置超出链表长度");

return;

}

newNode.next = current.next;

current.next = newNode;

}

4. 删除节点

java

public void deleteNode(int position) {

if (head == null) {

System.out.println("链表为空");

return;

}

if (position == 0) {

head = head.next;

return;

}

Node current = head;

int i = 0;

while (current.next != null && i < position – 1) {

current = current.next;

i++;

}

if (current.next == null) {

System.out.println("删除位置超出链表长度");

return;

}

current.next = current.next.next;

}

5. 查找节点

java

public int findNode(int data) {

Node current = head;

while (current != null) {

if (current.data == data) {

return 1;

}

current = current.next;

}

return 0;

}

6. 反转链表

java

public void reverseList() {

Node prev = null;

Node current = head;

Node next = null;

while (current != null) {

next = current.next;

current.next = prev;

prev = current;

current = next;

}

head = prev;

}

四、

链表作为计算机专业面试中的常见掌握链表的基本操作对于面试来说至关重要。本文通过介绍链表的基本概念和操作，帮助面试者更好地准备面试。在实际面试中，面试官可能会针对链表的各种操作进行提问，面试者熟练掌握链表的相关知识，以便在面试中表现出色。