define

The chain storage structure of a linear list uses a set of arbitrary storage units to store the data elements of a linear list. These units can be scattered anywhere in memory, that is, two logically adjacent elements are not required to be physically adjacent. Instead, the logical relationships between data elements are established through “chains”.

  • Because they are not necessarily physically adjacent, each data element, in addition to storing its own information, needs to store information indicating its immediate successors;
  • The domain that stores information about data elements is called a data domain;
  • The domain where the immediate successor is stored is called a pointer field, and the information in it is called a pointer or chain;
  • Data domain and pointer domain combine together, called node;
  • N nodes are linked into a linked list, that is, a linear list (A1, A2, A3… , an) chain storage structure;
  • In general, each node in a linked list can contain several data fields and several pointer fields. If each node contains only one pointer field, it is called a singly linked list.
  • The location of the first node (or head node) in the linked list is called the head pointer, and the last node pointer is NULL.
  • To facilitate various operations, you can add a node, called a header, before the first node in a singly linked list.

type data interface{}

type Node struct {
	Data data / / data domain
	Next *Node / / pointer field
}

type LinkList struct {
	Head *Node
	len int
}

// Initialize a linked list
func New(a) *LinkList {
	l := &LinkList{Head: &Node{}}
	l.len = 0
	return l
}
Copy the code

The main operating

To find the

Search is divided into search by value, and search by serial number, but the idea of the algorithm is basically the same:

1. Start from the table header to determine whether the current node meets the search conditions;

2. If not, move the pointer back one bit to point to the next node and continue to judge the condition;

3, find the node that meets the search criteria, exit the loop, return the node, if not found, return null

// Use the serial number
func (l *LinkList) FindKth(k int) *Node {
	if k < 1 || k > l.len {
		return nil
	}
	current := l.Head
	for i := 1; i <= k; i++ {
		current = current.Next
	}
	return current
}

// search by value
func (l *LinkList) Find(value data) *Node {
	forcurrent := l.Head; current ! =nil; current = current.Next {
		if current.Data == value {
			return current
		}
	}
	return nil
}
Copy the code
  • The time complexity of both algorithms is O(n).
  • Both loops use “working pointer fallback”, a common technique in many algorithms

insert

Insert a new node with value X after node i-1(1<= I <=n+1).

1. Construct a new node S;

2. Find node P at i-1;

3, modify pointer, insert new node.

The third step is shown in the figure:

s.Next = p.Next // create a link at 1
p.Next = s // create a link at 2
Copy the code

What if I switched the order of these two lines of code?

P.ext = s, which points to s, and s.ext = p.ext, which is already s, so it becomes s.ext = s. At that point insertion will fail. So these two sentences can not be inverted on any account.

func (l *LinkList) Insert(value data, i int) bool {
	preNode := l.FindKth(i - 1)
	if preNode == nil {
		return false
	}
	node := &Node{Data: value}
	node.Next = preNode.Next
	preNode.Next = node
	l.len++
	return true
}
Copy the code
  • The algorithm’s time depends on the I position, so it’s O(n).

delete

Delete the node at the I (1<= I <=n) position of the linked list.

1. Find node i-1, p;

2. Use S to save the node of P. ext, namely the ith node;

3. Connect p. ext to S. ext to disconnect the node;

4, save s with e, release S node, return e.

func (l *LinkList) Delete(i int) (data, bool) {
	preNode := l.FindKth(i - 1)
	if preNode == nil {
		return nil.false
	}
	deleteNode := preNode.Next
	preNode.Next = deleteNode.Next
	value := deleteNode.Data
	deleteNode = nil
	l.len--
	return value, true
}
Copy the code
  • The algorithm’s time depends on the I position, so it’s O(n).

The whole table creation

We can create linked lists using either a head plug or a tail plug.

The first interpolation

That is, when creating a linked list, each element is inserted sequentially in the head of the list.

Add a method called InsertHead that inserts an element in the head of the list.

2. Use InsertHead, in turn, to add elements to the list.

func (l *LinkList) InsertHead(value data) {
	node := &Node{Data: value}
	node.Next = l.Head.Next
	l.Head.Next = node
	l.len++
}

// create a header
l := LinkList.New()
for i := 1; i <= 5; i++ {
    // Insert 1 through 5 into the table header
    l.InsertHead(i)
}
Copy the code

See the structure of the linked list:

The tail interpolation

That is, when creating a linked list, each element is inserted sequentially at the end of the list.

1, add a method to the list to insert an element in the header, InsertTail;

2. Use InsertTail in turn to add elements to the list.

func (l *LinkList) InsertTail(value data) {
	node := &Node{Data: value}
	current := l.Head
	forcurrent.Next ! =nil {
		current = current.Next
	}
	current.Next = node
	l.len++
}

// create a tail insert
l := LinkList.New()
for i := 1; i <= 5; i++ {
    // Insert 1 through 5 at the end of the table
	l.InsertTail(i)
}
Copy the code

Linked list structure:

conclusion

Let’s compare the chain storage and sequential storage of linear tables in time and space:

time

Looking for:

  • Sequential storage structure O(1)
  • Singly linked lists O (n)

Insert and delete:

  • Sequential storage structures require an average move of half the length of the table in order (n) time
  • The insertion and deletion time of a single linked list is only O(1) after calculating a pointer at a certain position.
  • For example, if you insert 10 elements in a row at position I, for sequential storage, you move the next element every time you insert, so it’s O(n) every time.
  • Singly linked lists, you only find the I position the first time, which is O(n), and then all the insertions are O(1).

space

  • Sequential storage structures require pre-allocation of space, which may result in space waste if the allocation is large, and overflow if the allocation is small
  • Single-linked lists do not require pre-allocation of space, as long as there is still space can be allocated, and the number of elements is not limited

conclusion

  • If linear tables require frequent look-ups and few inserts and deletions, sequential storage is suitable.
  • If frequent insertions and deletions are required, single-linked lists are suitable.
  • If you know the length of a linear list in advance, you can use sequential storage; otherwise, you can use a single linked list.
  • There is no silver bullet — both have their advantages and disadvantages, and we should choose the appropriate storage structure according to the actual situation.

Thanks!