导入
链表的实现
本课程提供了链表的实现。
在继续学习与链表相关的挑战之前，我们先来看一下链表节点和链表类的实现。这些类将在本章后续的所有挑战中被预先使用。
LinkedListNode 类的实现
C++
1struct LinkedListNode { 2 int data; 3 LinkedListNode* next; 4 LinkedListNode* arbitrary_pointer; 5 LinkedListNode(int d) { 6 data = d; 7 next = nullptr; 8 arbitrary_pointer = nullptr; 9 } 10};
Java
1class LinkedListNode { 2 public int data; 3 public LinkedListNode next; 4 public LinkedListNode prev; 5 public LinkedListNode arbitraryPointer; 6 7 public LinkedListNode(int data) { 8 this.data = data; 9 this.next = null; 10 this.prev = null; 11 this.arbitraryPointer = null; 12 } 13}
Python
1class LinkedListNode: 2 def __init__(self, data): 3 self.data = data 4 self.next = None 5 self.arbitrary = None
JS
1let linkedListNode = function(data){ 2 this.data = data; 3 this.next = null; 4 this.arbitrary = null; 5}
Ruby
1class LinkedListNode 2 attr_accessor :data, :next, :arbitrary 3 4 def initialize(data) 5 @data = data 6 @next = nil 7 @arbitrary = nil 8 end 9end
Go
1type LinkedListNode struct { 2 data int 3 next *LinkedListNode 4 arbitrary *LinkedListNode 5}
LinkedList 类的实现
C++
1#include <iostream> 2#include <string> 3#include <vector> 4 5#include "LinkedListNode.cpp" 6 7using namespace std; 8 9class LinkedList { 10public: 11 LinkedListNode* head; 12 13 LinkedList() { head = nullptr; } 14 // InsertAtHead 方法将在链表头部插入一个整数元素。 15 void InsertAtHead(int data) { 16 if (head == nullptr) { 17 head = new LinkedListNode(data); 18 } else { 19 LinkedListNode* new_node = new LinkedListNode(data); 20 new_node->next = head; 21 head = new_node; 22 } 23 } 24 // InsertAtTail 方法将在链表尾部插入一个整数元素。 25 void InsertAtTail(int data) { 26 if (head == nullptr) { 27 head = new LinkedListNode(data); 28 } else { 29 LinkedListNode* new_node = new LinkedListNode(data); 30 LinkedListNode* temp = head; 31 while (temp->next != nullptr) { 32 temp = temp->next; 33 } 34 temp->next = new_node; 35 } 36 } 37 /* CreateLinkedList 方法将使用给定的整数数组，通过 InsertAtHead 方法创建链表。 */ 38 void CreateLinkedList(vector<int>& vec) { 39 for (int i = vec.size() - 1; i >= 0; i--) { 40 InsertAtHead(vec[i]); 41 } 42 } 43 // DisplayList 方法将显示链表中的元素。 44 void DisplayList() { 45 LinkedListNode* temp = head; 46 string result = "["; 47 while (temp != nullptr) { 48 result += to_string(temp->data); 49 temp = temp->next; 50 if (temp != nullptr) { 51 result += ", "; 52 } 53 } 54 cout << result << "]"; 55 } 56};
Java
1import java.util.*; 2 3class LinkedList { 4 public LinkedListNode head; 5 6 public LinkedList() { 7 this.head = null; 8 } 9 // insertAtHead 方法将在链表头部插入一个整数元素。 10 public void insertAtHead(int data) { 11 if (this.head == null) { 12 this.head = new LinkedListNode(data); 13 } else { 14 LinkedListNode newNode = new LinkedListNode(data); 15 newNode.next = this.head; 16 this.head = newNode; 17 } 18 } 19 // insertAtTail 方法将在链表尾部插入一个整数元素。 20 public void insertAtTail(int data) { 21 if (this.head == null) { 22 this.head = new LinkedListNode(data); 23 } else { 24 LinkedListNode newNode = new LinkedListNode(data); 25 LinkedListNode temp = this.head; 26 while (temp.next != null) { 27 temp = temp.next; 28 } 29 temp.next = newNode; 30 } 31 } 32 /* createLinkedList 方法将使用给定的整数列表，通过 insertAtHead 方法创建链表。 */ 33 public void createLinkedList(List<Integer> lst) { 34 for (int i = lst.size() - 1; i >= 0; i--) { 35 insertAtHead(lst.get(i)); 36 } 37 } 38 // displayLinkedList 方法将显示链表中的元素。 39 public void displayLinkedList() { 40 LinkedListNode temp = this.head; 41 StringBuilder res = new StringBuilder("["); 42 while (temp != null) { 43 res.insert(res.length(), temp.data); 44 temp = temp.next; 45 if (temp != null) { 46 res.insert(res.length(), ", "); 47 } 48 } 49 res.insert(res.length(), "]"); 50 System.out.println(res.toString()); 51 } 52}
Python
1from linked_list_node import * 2 3class Pair: 4 def __init__(self, first, second): 5 self.first = first 6 self.second = second 7 8class LinkedList: 9 def __init__(self): 10 self.head = None 11 # insert_at_head 方法将在链表头部插入一个整数元素。 12 def insert_at_head(self, data): 13 self.insert_node_at_head(LinkedListNode(data)) 14 # insert_node_at_head 方法将在链表头部插入一个 LinkedListNode。 15 def insert_node_at_head(self, node): 16 if not self.head: 17 self.head = node 18 else: 19 node.next = self.head 20 self.head = node 21 # insert_at_tail 方法将在链表尾部插入一个整数元素。 22 def insert_at_tail(self, node): 23 temp = self.head 24 while temp.next: 25 temp = temp.next 26 temp.next = node 27 # create_linked_list 方法将使用给定的整数列表，通过 insert_at_head 方法创建链表。 28 def create_linked_list(self, lst): 29 for x in reversed(lst): 30 new_node = LinkedListNode(x) 31 self.insert_node_at_head(new_node) 32 # __str__ 方法将显示链表中的元素。 33 def __str__(self): 34 result = "[" 35 temp = self.head 36 while temp: 37 result += str(temp.data) 38 temp = temp.next 39 if temp: 40 result += ", " 41 result += "]" 42 return result
JS
1import {LinkedListNode} from './LinkedListNode.js'; 2 3class LinkedList { 4 constructor() { 5 this.head = null; 6 } 7 // insertAtHead 方法将在链表头部插入一个整数元素。 8 insertAtHead(data) { 9 let newNode = new LinkedListNode(data); 10 if (this.head == null) { 11 this.head = newNode; 12 } else { 13 newNode.next = this.head; 14 this.head = newNode; 15 } 16 } 17 // insertAtTail 方法将在链表尾部插入一个整数元素。 18 insertAtTail(head, node) { 19 if (!head) { 20 return node; 21 } 22 let temp = head; 23 while (temp.next) { 24 temp = temp.next; 25 } 26 temp.next = node; 27 } 28 /* createLinkedList 方法将使用给定的整数数组，通过 insertAtHead 方法创建链表。 */ 29 createLinkedList(lst) { 30 let listHead = null; 31 lst.reverse(); 32 for (let x = 0; x < lst.length; x++) { 33 listHead = this.insertAtHead(lst[x]); 34 } 35 } 36 // displayLinkedList 方法将显示链表中的元素。 37 displayLinkedList() { 38 let temp = this.head; 39 let s = ""; 40 s += "["; 41 while (temp) { 42 s += temp.data; 43 temp = temp.next; 44 if (temp) { 45 s += ", "; 46 } 47 } 48 s += "]"; 49 return s; 50 } 51} 52export { LinkedList };
Ruby
1require './linked_list_node' 2 3class LinkedList 4 attr_accessor :head 5 6 # initialize 将初始化 LinkedList 的数据成员 7 def initialize(param = nil) 8 @head = param 9 end 10 11 # insert_at_head 方法将在链表头部插入一个整数元素。 12 def insert_at_head(data) 13 insert_node_at_head(LinkedListNode.new(data)) 14 end 15 16 # insert_node_at_head 方法将在链表头部插入一个 LinkedListNode。 17 def insert_node_at_head(node) 18 if @head 19 node.next = @head 20 @head = node 21 else 22 @head = node 23 end 24 end 25 26 # insert_at_tail 方法将在链表尾部插入一个整数元素。 27 def insert_at_tail(data) 28 insert_node_at_tail(LinkedListNode.new(data)) 29 end 30 31 # insert_node_at_tail 方法将在链表尾部插入一个 LinkedListNode。 32 def insert_node_at_tail(node) 33 if @head 34 temp = @head 35 temp = temp.next while temp.next 36 temp.next = node 37 else 38 @head = node 39 end 40 end 41 42 # create_linked_list 方法将使用给定的整数数组，通过 insert_at_head 方法创建链表。 43 def create_linked_list(lst) 44 list_head = nil 45 lst.reverse.each { |x| list_head = insert_at_head(x) } 46 end 47 48 # display_linkedlist 方法将显示链表中的元素。 49 def display_linkedlist() 50 print "[" 51 temp = @head 52 while temp 53 print temp.data.to_s 54 temp = temp.next 55 print ", " if temp 56 end 57 print "]" 58 end 59end
Go
1package main 2import ( 3 "fmt" 4) 5 6// LinkedList 结构体用于创建 LinkedList 类型的对象。 7type LinkedList struct { 8 head *LinkedListNode 9} 10 11// InsertAtHead 方法将在链表头部插入一个整数元素。 12func (l *LinkedList) InsertAtHead(data int) { 13 l.InsertNodeAtHead(&LinkedListNode{data: data}) 14} 15 16// InsertNodeAtHead 方法将在链表头部插入一个 LinkedListNode。 17func (l *LinkedList) InsertNodeAtHead(node *LinkedListNode) { 18 if l.head == nil { 19 l.head = node 20 } else { 21 node.next = l.head 22 l.head = node 23 } 24} 25 26// InsertAtTail 方法将在链表尾部插入一个整数元素。 27func (l *LinkedList) InsertAtTail(data int) { 28 l.InsertNodeAtTail(&LinkedListNode{data: data}) 29} 30 31// InsertNodeAtTail 方法将在链表尾部插入一个 LinkedListNode。 32func (l *LinkedList) InsertNodeAtTail(node *LinkedListNode) { 33 if l.head == nil { 34 l.head = node 35 } else { 36 temp := l.head 37 for temp.next != nil { 38 temp = temp.next 39 } 40 temp.next = node 41 } 42} 43 44/* CreateLinkedList 方法将使用给定的整数数组，通过 InsertAtHead 方法创建链表。 */ 45func (l *LinkedList) CreateLinkedList(lst []int) { 46 for i := len(lst) - 1; i >= 0; i-- { 47 l.InsertAtHead(lst[i]) 48 } 49} 50 51// DisplayLinkedList 方法将显示链表中的元素。 52func (l *LinkedList) DisplayLinkedList() { 53 temp := l.head 54 fmt.Print("[") 55 for temp != nil { 56 fmt.Print(temp.data) 57 temp = temp.next 58 if temp != nil { 59 fmt.Print(", ") 60 } 61 } 62 fmt.Print("]") 63}